From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 6372B396D823; Fri, 13 May 2022 13:47:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6372B396D823 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-434] Make range_from_dom more effective. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: b584cbdb0829bb0ad4e6ed7488a304ae4e76b870 X-Git-Newrev: 6b156044c12bc4582511fe270b10450c943476dd Message-Id: <20220513134752.6372B396D823@sourceware.org> Date: Fri, 13 May 2022 13:47:52 +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: Fri, 13 May 2022 13:47:52 -0000 https://gcc.gnu.org/g:6b156044c12bc4582511fe270b10450c943476dd commit r13-434-g6b156044c12bc4582511fe270b10450c943476dd Author: Andrew MacLeod Date: Thu Mar 24 15:28:43 2022 -0400 Make range_from_dom more effective. Add modes to range_from_dom such that we can simply query, or adjust the cache and deal with multiple predecessor blocks. * gimple-range-cache.cc (ranger_cache::ranger_cache): Start with worlist truncated. (ranger_cache::entry_range): Add rfd_mode parameter. (ranger_cache::exit_range): Ditto. (ranger_cache::edge_range): New. Incorporate from range_on_edge. (ranger_cache::range_of_expr): Adjust call to entry_range. (ranger_cache::range_on_edge): Split to edge_range and call. (ranger_cache::fill_block_cache): Always invoke range_from_dom. (ranger_cache::range_from_dom): Make reentrant, add search mode, handle mutiple predecessors. (ranger_cache::update_to_nonnull): Adjust call to exit_range. * gimple-range-cache.h (ranger_cache): Add enum rfd_mode. Adjust prototypes. Diff: --- gcc/gimple-range-cache.cc | 135 ++++++++++++++++++++++++++++++---------------- gcc/gimple-range-cache.h | 13 +++-- 2 files changed, 98 insertions(+), 50 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 421ea1a20ef..bdb30460345 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -864,6 +864,7 @@ ranger_cache::ranger_cache (int not_executable_flag) { m_workback.create (0); m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_workback.truncate (0); m_temporal = new temporal_cache; // If DOM info is available, spawn an oracle as well. if (dom_info_available_p (CDI_DOMINATORS)) @@ -1008,10 +1009,12 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb) } } -// Get the range of NAME as it occurs on entry to block BB. +// Get the range of NAME as it occurs on entry to block BB. Use MODE for +// lookups. void -ranger_cache::entry_range (irange &r, tree name, basic_block bb) +ranger_cache::entry_range (irange &r, tree name, basic_block bb, + enum rfd_mode mode) { if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) { @@ -1022,13 +1025,16 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb) // Look for the on-entry value of name in BB from the cache. // Otherwise pick up the best available global value. if (!m_on_entry.get_bb_range (r, name, bb)) - range_of_def (r, name); + if (!range_from_dom (r, name, bb, mode)) + range_of_def (r, name); } -// Get the range of NAME as it occurs on exit from block BB. +// Get the range of NAME as it occurs on exit from block BB. Use MODE for +// lookups. void -ranger_cache::exit_range (irange &r, tree name, basic_block bb) +ranger_cache::exit_range (irange &r, tree name, basic_block bb, + enum rfd_mode mode) { if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) { @@ -1041,8 +1047,25 @@ ranger_cache::exit_range (irange &r, tree name, basic_block bb) if (def_bb == bb) range_of_def (r, name, bb); else - entry_range (r, name, bb); - } + entry_range (r, name, bb, mode); +} + +// Get the range of NAME on edge E using MODE, return the result in R. +// Always returns a range and true. + +bool +ranger_cache::edge_range (irange &r, edge e, tree name, enum rfd_mode mode) +{ + exit_range (r, name, e->src, mode); + // If this is not an abnormal edge, check for a non-null exit. + if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) + m_non_null.adjust_range (r, name, e->src, false); + int_range_max er; + if (m_gori.outgoing_edge_range_p (er, e, name, *this)) + r.intersect (er); + return true; +} + // Implement range_of_expr. @@ -1063,32 +1086,22 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt) if (bb == def_bb) range_of_def (r, name, bb); else - entry_range (r, name, bb); + entry_range (r, name, bb, RFD_NONE); return true; } -// Implement range_on_edge. Always return the best available range. - - bool - ranger_cache::range_on_edge (irange &r, edge e, tree expr) - { - if (gimple_range_ssa_p (expr)) - { - exit_range (r, expr, e->src); - // If this is not an abnormal edge, check for a non-null exit. - if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) - m_non_null.adjust_range (r, expr, e->src, false); - int_range_max edge_range; - if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this)) - r.intersect (edge_range); - return true; - } +// Implement range_on_edge. Always return the best available range using +// the current cache values. +bool +ranger_cache::range_on_edge (irange &r, edge e, tree expr) +{ + if (gimple_range_ssa_p (expr)) + return edge_range (r, e, expr, RFD_NONE); return get_tree_range (r, expr, NULL); } - // Return a static range for NAME on entry to basic block BB in R. If // calc is true, fill any cache entries required between BB and the // def block for NAME. Otherwise, return false if the cache is empty. @@ -1281,20 +1294,12 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // At this point we shouldn't be looking at the def, entry or exit block. gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + gcc_checking_assert (m_workback.length () == 0); // If the block cache is set, then we've already visited this block. if (m_on_entry.bb_range_p (name, bb)) return; - // Visit each block back to the DEF. Initialize each one to UNDEFINED. - // m_visited at the end will contain all the blocks that we needed to set - // the range_on_entry cache for. - m_workback.truncate (0); - m_workback.quick_push (bb); - undefined.set_undefined (); - m_on_entry.set_bb_range (name, bb, undefined); - gcc_checking_assert (m_update->empty_p ()); - if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "\n"); @@ -1302,9 +1307,8 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " : "); } - // If there are dominators, check if a dominators can supply the range. - if (dom_info_available_p (CDI_DOMINATORS) - && range_from_dom (block_result, name, bb)) + // Check if a dominators can supply the range. + if (range_from_dom (block_result, name, bb, RFD_FILL)) { m_on_entry.set_bb_range (name, bb, block_result); if (DEBUG_RANGE_CACHE) @@ -1313,9 +1317,18 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) block_result.dump (dump_file); fprintf (dump_file, "\n"); } + gcc_checking_assert (m_workback.length () == 0); return; } + // Visit each block back to the DEF. Initialize each one to UNDEFINED. + // m_visited at the end will contain all the blocks that we needed to set + // the range_on_entry cache for. + m_workback.quick_push (bb); + undefined.set_undefined (); + m_on_entry.set_bb_range (name, bb, undefined); + gcc_checking_assert (m_update->empty_p ()); + while (m_workback.length () > 0) { basic_block node = m_workback.pop (); @@ -1399,12 +1412,14 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } -// Get the range of NAME from dominators of BB and return it in R. +// Get the range of NAME from dominators of BB and return it in R. Search the +// dominator tree based on MODE. bool -ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb) +ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb, + enum rfd_mode mode) { - if (!dom_info_available_p (CDI_DOMINATORS)) + if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS)) return false; // Search back to the definition block or entry block. @@ -1419,7 +1434,7 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb) // Range on entry to the DEF block should not be queried. gcc_checking_assert (start_bb != def_bb); - m_workback.truncate (0); + unsigned start_limit = m_workback.length (); // Default value is global range. get_global_range (r, name); @@ -1436,10 +1451,36 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb) if (m_gori.has_edge_range_p (name, bb)) { // Only outgoing ranges to single_pred blocks are dominated by - // outgoing edge ranges, so only those need to be considered. + // 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, + // store the range, then calculate the incoming range for PREV_BB. + if (def_bb != bb) + { + 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; + int_range_max er; + 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; + } } if (def_bb == bb) @@ -1460,16 +1501,16 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb) } // Now process any outgoing edges that we seen along the way. - while (m_workback.length () > 0) + while (m_workback.length () > start_limit) { - int_range_max edge_range; + int_range_max er; prev_bb = m_workback.pop (); edge e = single_pred_edge (prev_bb); bb = e->src; - if (m_gori.outgoing_edge_range_p (edge_range, e, name, *this)) + if (m_gori.outgoing_edge_range_p (er, e, name, *this)) { - r.intersect (edge_range); + r.intersect (er); if (r.varying_p () && ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)) { if (m_non_null.non_null_deref_p (name, bb, false)) @@ -1518,7 +1559,7 @@ ranger_cache::update_to_nonnull (basic_block bb, tree name) // Update the on-entry cache for BB to be non-zero. Note this can set // the on entry value in the DEF block, which can override the def. int_range_max r; - exit_range (r, name, bb); + exit_range (r, name, bb, RFD_READ_ONLY); if (r.varying_p ()) { r.set_nonzero (type); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index a0244e4f6a4..560403b534e 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -129,7 +129,6 @@ public: virtual bool range_of_expr (irange &r, tree name, gimple *stmt); virtual bool range_on_edge (irange &r, edge e, tree expr); bool block_range (irange &r, basic_block bb, tree name, bool calc = true); - bool range_from_dom (irange &r, tree name, basic_block bb); bool get_global_range (irange &r, tree name) const; bool get_global_range (irange &r, tree name, bool ¤t_p); @@ -151,9 +150,17 @@ private: void fill_block_cache (tree name, basic_block bb, basic_block def_bb); void propagate_cache (tree name); + enum rfd_mode + { + RFD_NONE, // Only look at current block cache. + RFD_READ_ONLY, // Scan DOM tree, do not write to cache. + RFD_FILL // Scan DOM tree, updating important nodes. + }; + bool range_from_dom (irange &r, tree name, basic_block bb, enum rfd_mode); void range_of_def (irange &r, tree name, basic_block bb = NULL); - void entry_range (irange &r, tree expr, basic_block bb); - void exit_range (irange &r, tree expr, basic_block bb); + void entry_range (irange &r, tree expr, basic_block bb, enum rfd_mode); + void exit_range (irange &r, tree expr, basic_block bb, enum rfd_mode); + bool edge_range (irange &r, edge e, tree name, enum rfd_mode); vec m_workback; class update_list *m_update;