From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 6232B3858435; Fri, 5 Nov 2021 17:16:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6232B3858435 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 r12-4947] Abstract ranger cache update list. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: a79fe53d6ce6074d083e925b6b19773e45817405 X-Git-Newrev: 98244c68e77cf75f93b66ee02df059f718c3fbc0 Message-Id: <20211105171637.6232B3858435@sourceware.org> Date: Fri, 5 Nov 2021 17:16:37 +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, 05 Nov 2021 17:16:37 -0000 https://gcc.gnu.org/g:98244c68e77cf75f93b66ee02df059f718c3fbc0 commit r12-4947-g98244c68e77cf75f93b66ee02df059f718c3fbc0 Author: Andrew MacLeod Date: Thu Nov 4 15:08:06 2021 -0400 Abstract ranger cache update list. Make it more efficient by removing the call to vec::contains. PR tree-optimization/102943 * gimple-range-cache.cc (class update_list): New. (update_list::add): Replace add_to_update. (update_list::pop): New. (ranger_cache::ranger_cache): Adjust. (ranger_cache::~ranger_cache): Adjust. (ranger_cache::add_to_update): Delete. (ranger_cache::propagate_cache): Adjust to new class. (ranger_cache::propagate_updated_value): Ditto. (ranger_cache::fill_block_cache): Ditto. * gimple-range-cache.h (class ranger_cache): Adjust to update class. Diff: --- gcc/gimple-range-cache.cc | 129 +++++++++++++++++++++++++++++++++++----------- gcc/gimple-range-cache.h | 4 +- 2 files changed, 100 insertions(+), 33 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 05010cf15bc..e5591bab0ef 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -754,14 +754,96 @@ temporal_cache::set_always_current (tree name) // -------------------------------------------------------------------------- +// This class provides an abstraction of a list of blocks to be updated +// by the cache. It is currently a stack but could be changed. It also +// maintains a list of blocks which have failed propagation, and does not +// enter any of those blocks into the list. + +// A vector over the BBs is maintained, and an entry of 0 means it is not in +// a list. Otherwise, the entry is the next block in the list. -1 terminates +// the list. m_head points to the top of the list, -1 if the list is empty. + +class update_list +{ +public: + update_list (); + ~update_list (); + void add (basic_block bb); + basic_block pop (); + inline bool empty_p () { return m_update_head == -1; } + inline void clear_failures () { bitmap_clear (m_propfail); } + inline void propagation_failed (basic_block bb) + { bitmap_set_bit (m_propfail, bb->index); } +private: + vec m_update_list; + int m_update_head; + bitmap m_propfail; +}; + +// Create an update list. + +update_list::update_list () +{ + m_update_list.create (0); + m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64); + m_update_head = -1; + m_propfail = BITMAP_ALLOC (NULL); +} + +// Destroy an update list. + +update_list::~update_list () +{ + m_update_list.release (); + BITMAP_FREE (m_propfail); +} + +// Add BB to the list of blocks to update, unless it's already in the list. + +void +update_list::add (basic_block bb) +{ + int i = bb->index; + // If propagation has failed for BB, or its already in the list, don't + // add it again. + if ((unsigned)i >= m_update_list.length ()) + m_update_list.safe_grow_cleared (i + 64); + if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i)) + { + if (empty_p ()) + { + m_update_head = i; + m_update_list[i] = -1; + } + else + { + gcc_checking_assert (m_update_head > 0); + m_update_list[i] = m_update_head; + m_update_head = i; + } + } +} + +// Remove a block from the list. + +basic_block +update_list::pop () +{ + gcc_checking_assert (!empty_p ()); + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head); + int pop = m_update_head; + m_update_head = m_update_list[pop]; + m_update_list[pop] = 0; + return bb; +} + +// -------------------------------------------------------------------------- + ranger_cache::ranger_cache (int not_executable_flag) : m_gori (not_executable_flag) { m_workback.create (0); m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun)); - m_update_list.create (0); - m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun)); - m_update_list.truncate (0); m_temporal = new temporal_cache; // If DOM info is available, spawn an oracle as well. if (dom_info_available_p (CDI_DOMINATORS)) @@ -779,17 +861,16 @@ ranger_cache::ranger_cache (int not_executable_flag) if (bb) m_gori.exports (bb); } - m_propfail = BITMAP_ALLOC (NULL); + m_update = new update_list (); } ranger_cache::~ranger_cache () { - BITMAP_FREE (m_propfail); + delete m_update; if (m_oracle) delete m_oracle; delete m_temporal; m_workback.release (); - m_update_list.release (); } // Dump the global caches to file F. if GORI_DUMP is true, dump the @@ -1029,17 +1110,6 @@ ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc) return m_on_entry.get_bb_range (r, name, bb); } -// Add BB to the list of blocks to update, unless it's already in the list. - -void -ranger_cache::add_to_update (basic_block bb) -{ - // If propagation has failed for BB, or its already in the list, don't - // add it again. - if (!bitmap_bit_p (m_propfail, bb->index) && !m_update_list.contains (bb)) - m_update_list.quick_push (bb); -} - // If there is anything in the propagation update_list, continue // processing NAME until the list of blocks is empty. @@ -1053,16 +1123,15 @@ ranger_cache::propagate_cache (tree name) int_range_max current_range; int_range_max e_range; - gcc_checking_assert (bitmap_empty_p (m_propfail)); // Process each block by seeing if its calculated range on entry is // the same as its cached value. If there is a difference, update // the cache to reflect the new value, and check to see if any // successors have cache entries which may need to be checked for // updates. - while (m_update_list.length () > 0) + while (!m_update->empty_p ()) { - bb = m_update_list.pop (); + bb = m_update->pop (); gcc_checking_assert (m_on_entry.bb_range_p (name, bb)); m_on_entry.get_bb_range (current_range, name, bb); @@ -1097,7 +1166,7 @@ ranger_cache::propagate_cache (tree name) bool ok_p = m_on_entry.set_bb_range (name, bb, new_range); // If the cache couldn't set the value, mark it as failed. if (!ok_p) - bitmap_set_bit (m_propfail, bb->index); + m_update->propagation_failed (bb); if (DEBUG_RANGE_CACHE) { if (!ok_p) @@ -1119,7 +1188,7 @@ ranger_cache::propagate_cache (tree name) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, " bb%d",e->dest->index); - add_to_update (e->dest); + m_update->add (e->dest); } if (DEBUG_RANGE_CACHE) fprintf (dump_file, "\n"); @@ -1131,7 +1200,7 @@ ranger_cache::propagate_cache (tree name) print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, "\n"); } - bitmap_clear (m_propfail); + m_update->clear_failures (); } // Check to see if an update to the value for NAME in BB has any effect @@ -1146,7 +1215,7 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb) edge_iterator ei; // The update work list should be empty at this point. - gcc_checking_assert (m_update_list.length () == 0); + gcc_checking_assert (m_update->empty_p ()); gcc_checking_assert (bb); if (DEBUG_RANGE_CACHE) @@ -1160,12 +1229,12 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb) // Only update active cache entries. if (m_on_entry.bb_range_p (name, e->dest)) { - add_to_update (e->dest); + m_update->add (e->dest); if (DEBUG_RANGE_CACHE) fprintf (dump_file, " UPDATE: bb%d", e->dest->index); } } - if (m_update_list.length () != 0) + if (!m_update->empty_p ()) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "\n"); @@ -1205,7 +1274,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) m_workback.quick_push (bb); undefined.set_undefined (); m_on_entry.set_bb_range (name, bb, undefined); - gcc_checking_assert (m_update_list.length () == 0); + gcc_checking_assert (m_update->empty_p ()); if (DEBUG_RANGE_CACHE) { @@ -1235,7 +1304,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // If the pred block is the def block add this BB to update list. if (pred == def_bb) { - add_to_update (node); + m_update->add (node); continue; } @@ -1255,7 +1324,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "nonnull: update "); - add_to_update (node); + m_update->add (node); } // If the pred block already has a range, or if it can contribute @@ -1270,7 +1339,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } if (!r.undefined_p () || m_gori.has_edge_range_p (name, e)) { - add_to_update (node); + m_update->add (node); if (DEBUG_RANGE_CACHE) fprintf (dump_file, "update. "); } diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 75105008338..49c13d1e85f 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -114,7 +114,6 @@ private: ssa_global_cache m_globals; block_range_cache m_on_entry; class temporal_cache *m_temporal; - void add_to_update (basic_block bb); void fill_block_cache (tree name, basic_block bb, basic_block def_bb); void propagate_cache (tree name); @@ -122,9 +121,8 @@ private: void entry_range (irange &r, tree expr, basic_block bb); void exit_range (irange &r, tree expr, basic_block bb); - bitmap m_propfail; vec m_workback; - vec m_update_list; + class update_list *m_update; }; #endif // GCC_SSA_RANGE_CACHE_H