https://gcc.gnu.org/g:3f9e620b52003139f3942113804184b4be56cf31
commit r17-1236-g3f9e620b52003139f3942113804184b4be56cf31 Author: Richard Sandiford <[email protected]> Date: Tue Jun 2 20:50:27 2026 +0100 bitmap: Add bitmap_clear_last_set_bit This patch adds a bitmap_clear_last_set_bit routine, following the precedent and implementation approach of bitmap_clear_first_set_bit. gcc/ * bitmap.h: Document the complexity of pop_largest aka bitmap_clear_last_set_bit. (bitmap_clear_last_set_bit): Declare. * bitmap.cc (bitmap_last_set_bit_worker): New function, split out from... (bitmap_last_set_bit): ...here. (bitmap_clear_last_set_bit): New function. Diff: --- gcc/bitmap.cc | 45 +++++++++++++++++++++++++++++++++++++++------ gcc/bitmap.h | 3 +++ 2 files changed, 42 insertions(+), 6 deletions(-) diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc index fb5203081f8c..91c1019cb34c 100644 --- a/gcc/bitmap.cc +++ b/gcc/bitmap.cc @@ -1308,13 +1308,13 @@ bitmap_clear_first_set_bit (bitmap a) return bitmap_first_set_bit_worker (a, true); } -/* Return the bit number of the first set bit in the bitmap. The - bitmap must be non-empty. */ +/* Return the bit number of the last set bit in the bitmap. The bitmap + must be non-empty. When CLEAR is true, also clear the bit. */ -unsigned -bitmap_last_set_bit (const_bitmap a) +static unsigned +bitmap_last_set_bit_worker (bitmap a, bool clear) { - const bitmap_element *elt; + bitmap_element *elt; unsigned bit_no; BITMAP_WORD word; int ix; @@ -1355,8 +1355,41 @@ bitmap_last_set_bit (const_bitmap a) bit_no += bitmap_popcount (x) - 1; #endif - return bit_no; + if (clear) + { + elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS)); + /* If we cleared the entire word, free up the element. */ + if (!elt->bits[ix] + && bitmap_element_zerop (elt)) + { + if (!a->tree_form) + bitmap_list_unlink_element (a, elt); + else + bitmap_tree_unlink_element (a, elt); + } + } + + return bit_no; } + +/* Return the bit number of the last set bit in the bitmap. + The bitmap must be non-empty. */ + +unsigned +bitmap_last_set_bit (const_bitmap a) +{ + return bitmap_last_set_bit_worker (const_cast<bitmap> (a), false); +} + +/* Return and clear the bit number of the last set bit in the bitmap. + The bitmap must be non-empty. */ + +unsigned +bitmap_clear_last_set_bit (bitmap a) +{ + return bitmap_last_set_bit_worker (a, true); +} + /* DST = A & B. */ diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 35f0bd060c1e..fbf0b6366ebb 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -128,6 +128,7 @@ along with GCC; see the file COPYING3. If not see * largest_member : bitmap_last_set_bit (but this could in constant time with a pointer to the last element in the chain) + * pop_largest : bitmap_clear_last_set_bit * set_size : bitmap_last_set_bit In tree view the following operations can all be performed in O(log E) @@ -136,6 +137,7 @@ along with GCC; see the file COPYING3. If not see * smallest_member * pop_smallest * largest_member + * pop_largest * set_size * member_p * add_member @@ -505,6 +507,7 @@ extern void debug (const bitmap_head *ptr); extern unsigned bitmap_first_set_bit (const_bitmap); extern unsigned bitmap_clear_first_set_bit (bitmap); extern unsigned bitmap_last_set_bit (const_bitmap); +extern unsigned bitmap_clear_last_set_bit (bitmap); /* Compute bitmap hash (for purposes of hashing etc.) */ extern hashval_t bitmap_hash (const_bitmap);
