https://gcc.gnu.org/g:6ec6de8fcda3e68526c4630ddc0fed55bbc2966a
commit r17-1348-g6ec6de8fcda3e68526c4630ddc0fed55bbc2966a Author: Richard Sandiford <[email protected]> Date: Thu Jun 4 16:40:44 2026 +0100 bitmap: Avoid amortised O(E) behaviour for tree first/last bit The comments in bitmap.h say that bitmap_first_set_bit and bitmap_last_set_bit are amortised O(logE) and worst-case O(E). But the implementation just does a simple pointer chase, without any splaying. This can be amortised O(E) if, for example, code sets bits in ascending order and then repeatedly tests for the first bit. Nothing would then move the root away from the last element or begin to balance the tree. gcc/ * bitmap.cc: Include pretty-print.h and splay-tree-utils.h. (bitmap_splay_tree_accessors): New class. (bitmap_splay_tree): New type. (bitmap_first_set_bit_worker): Use bitmap_splay_tree::min_node for tree views. (bitmap_last_set_bit_worker): Use bitmap_splay_tree::max_node for tree views. Diff: --- gcc/bitmap.cc | 31 +++++++++++++++++++++++-------- 1 file changed, 23 insertions(+), 8 deletions(-) diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc index fdea7200f1da..476358c12764 100644 --- a/gcc/bitmap.cc +++ b/gcc/bitmap.cc @@ -22,6 +22,22 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "bitmap.h" #include "selftest.h" +#include "pretty-print.h" +#include "splay-tree-utils.h" + +class bitmap_splay_tree_accessors +{ +public: + using node_type = bitmap_element *; + + static node_type &child (node_type node, unsigned int index) + { + return index ? node->next : node->prev; + } +}; + +using bitmap_splay_tree + = splay_tree_without_parent<bitmap_splay_tree_accessors>; /* Memory allocation statistics purpose instance. */ mem_alloc_description<bitmap_usage> bitmap_mem_desc; @@ -1235,8 +1251,7 @@ bitmap_first_set_bit_worker (bitmap a, bool clear) gcc_checking_assert (elt); if (a->tree_form) - while (elt->prev) - elt = elt->prev; + elt = a->first = bitmap_splay_tree (elt).min_node (); bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) @@ -1322,13 +1337,13 @@ bitmap_last_set_bit_worker (bitmap a, bool clear) int ix; if (a->tree_form) - elt = a->first; + elt = a->first = bitmap_splay_tree (a->first).max_node (); else - elt = a->current ? a->current : a->first; - gcc_checking_assert (elt); - - while (elt->next) - elt = elt->next; + { + elt = a->current ? a->current : a->first; + while (elt->next) + elt = elt->next; + } bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
