The equivalence oracle contains lists of equivalence sets.
IN this case we now maintain a bitmap for each SSA_NAME indicating which blocks this name has relations registered in. There was already a vector indexed by ssa_names for a cached non-zero range, it was simply expanded to include a block_list bitmap when needed.
clear () now only visits each basic block in the bitmap. Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed. Andrew
From f4e297063c0c035eb300fa253812c42dcb4ac268 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod <[email protected]> Date: Thu, 20 Aug 2026 12:50:45 -0400 Subject: [PATCH 2/3] Improve equiv_oracle::clear performance. Add a bitmap indicting which blocks an ssa-name has an equivalence in. PR tree-optimization/126856 * value-relation.cc (equiv_oracle::equiv_oracle): Adjust for rename from m_self_equiv to m_name_info. (equiv_oracle::~equiv_oracle): Likewise. (equiv_oracle::register_equiv_block): New. (equiv_oracle::equiv_set): Adjust for rename. (equiv_oracle::register_equiv): Call register_equiv_block. (equiv_oracle::clear): Process just the required blocks. (equiv_oracle::add_equiv_to_block): Call register_equiv_block. * value-relation.h (class name_info): New. (equiv_oracle::m_self_equiv): Change type and Rename to m_name_info. (register_equiv_block): Declare. --- gcc/value-relation.cc | 70 +++++++++++++++++++++++++++++++++---------- gcc/value-relation.h | 12 +++++++- 2 files changed, 65 insertions(+), 17 deletions(-) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index b4b65e6cdc8..9bb0aab7fa1 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -317,8 +317,8 @@ equiv_oracle::equiv_oracle () m_equiv_set = BITMAP_ALLOC (&m_bitmaps); bitmap_tree_view (m_equiv_set); obstack_init (&m_chain_obstack); - m_self_equiv.create (0); - m_self_equiv.safe_grow_cleared (num_ssa_names + 1); + m_name_info.create (0); + m_name_info.safe_grow_cleared (num_ssa_names + 1); m_partial.create (0); m_partial.safe_grow_cleared (num_ssa_names + 1); // Create a bitmap to avoid registering multiple equivalences from a LHS. @@ -332,7 +332,7 @@ equiv_oracle::equiv_oracle () equiv_oracle::~equiv_oracle () { m_partial.release (); - m_self_equiv.release (); + m_name_info.release (); obstack_free (&m_chain_obstack, NULL); m_equiv.release (); bitmap_obstack_release (&m_bitmaps); @@ -451,6 +451,27 @@ equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const return VREL_VARYING; } +void +equiv_oracle::register_equiv_block (unsigned v, unsigned bbi) +{ + if (v >= m_name_info.length ()) + m_name_info.safe_grow_cleared (num_ssa_names + 1); + + if (!m_name_info[v].m_block_list) + m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps); + + bitmap_set_bit (m_name_info[v].m_block_list, bbi); +} + +void +equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb) +{ + bitmap_iterator bi; + unsigned v; + + EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi) + register_equiv_block (v, bb->index); +} // Find and return the equivalency set for SSA along the dominators of BB. // This is the external API. @@ -465,15 +486,15 @@ equiv_oracle::equiv_set (tree ssa, basic_block bb) // Otherwise return a cached equiv set containing just this SSA. unsigned v = SSA_NAME_VERSION (ssa); - if (v >= m_self_equiv.length ()) - m_self_equiv.safe_grow_cleared (num_ssa_names + 1); + if (v >= m_name_info.length ()) + m_name_info.safe_grow_cleared (num_ssa_names + 1); - if (!m_self_equiv[v]) + if (!m_name_info[v].m_self_equiv) { - m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps); - bitmap_set_bit (m_self_equiv[v], v); + m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps); + bitmap_set_bit (m_name_info[v].m_self_equiv, v); } - return m_self_equiv[v]; + return m_name_info[v].m_self_equiv; } // Query if there is a relation (equivalence) between 2 SSA_NAMEs. @@ -549,6 +570,8 @@ equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) { bitmap_set_bit (equiv->m_names, v); bitmap_set_bit (m_equiv[bb->index]->m_names, v); + // Add BB to V. + register_equiv_block (v, bb->index); return NULL; } @@ -557,6 +580,8 @@ equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) bitmap b = BITMAP_ALLOC (&m_bitmaps); valid_equivs (b, equiv->m_names, bb); bitmap_set_bit (b, v); + // Add BB to the all the equiv names. + register_equiv_block (b, bb); return b; } @@ -578,8 +603,12 @@ equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, if (equiv_2->m_bb == bb) bitmap_clear (equiv_2->m_names); else - // Ensure the new names are in the summary for BB. - bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); + { + // Ensure the new names are in the summary for BB. + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); + // Add BB to the names in equiv2. + register_equiv_block (equiv_2->m_names, bb); + } return NULL; } // If equiv_2 is in BB, use it for the combined set. @@ -588,6 +617,8 @@ equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, valid_equivs (equiv_2->m_names, equiv_1->m_names, bb); // Ensure the new names are in the summary. bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); + // Add BB to the names in equiv1. + register_equiv_block (equiv_1->m_names, bb); return NULL; } @@ -595,6 +626,8 @@ equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, bitmap b = BITMAP_ALLOC (&m_bitmaps); valid_equivs (b, equiv_1->m_names, bb); valid_equivs (b, equiv_2->m_names, bb); + // Add BB to the all the equiv names. + register_equiv_block (b, bb); return b; } @@ -627,15 +660,17 @@ void equiv_oracle::clear (tree name) { unsigned v = SSA_NAME_VERSION (name); - // Remove v from any equivalences. + // Remove NAME from any blocks it is an equivalence in. if (bitmap_bit_p (m_equiv_set, v)) { - basic_block bb; - FOR_EACH_BB_FN (bb, cfun) + gcc_checking_assert (m_name_info[v].m_block_list); + bitmap_iterator bi; + unsigned bbi; + + EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi) { - unsigned bbi = bb->index; if (bbi >= m_equiv.length ()) - continue; + break; if (!m_equiv[bbi]) continue; equiv_chain *ptr = m_equiv[bbi]->find (v); @@ -646,6 +681,7 @@ equiv_oracle::clear (tree name) } } bitmap_clear_bit (m_equiv_set, v); + bitmap_clear (m_name_info[v].m_block_list); } // Eliminate any partial equivs. if (v < m_partial.length ()) @@ -747,6 +783,8 @@ equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set) ptr->m_next = m_equiv[bb->index]->m_next; m_equiv[bb->index]->m_next = ptr; bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); + // Add BB to the equiv set. + register_equiv_block (equiv_set, bb); } // Make sure the BB vector is big enough and grow it if needed. diff --git a/gcc/value-relation.h b/gcc/value-relation.h index d150b0ac5b2..d57d0717b3e 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -191,7 +191,13 @@ protected: private: bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists. vec <equiv_chain *> m_equiv; // Index by BB. list of equivalences. - vec <bitmap> m_self_equiv; // Index by ssa-name, self equivalency set. + class name_info + { + public: + bitmap m_self_equiv; // Self equivalency set. + bitmap m_block_list; // BB's name occurs in equivalencies. + }; + vec <name_info> m_name_info; // Index by ssa-name. vec <pe_slice> m_partial; // Partial equivalencies. void limit_check (basic_block bb = NULL); @@ -201,6 +207,10 @@ private: bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1); bitmap register_equiv (basic_block bb, equiv_chain *equiv_1, equiv_chain *equiv_2); + + void register_equiv_block (unsigned v, unsigned bbi); + void register_equiv_block (const_bitmap equiv, basic_block bb); + void register_initial_def (tree ssa); void add_equiv_to_block (basic_block bb, bitmap equiv); }; -- 2.45.0
