Re: [RFA] pretty-ipa merge 7: bitmap_last_set_bit

[Richard Guenther <rguenther at suse dot de>]

On Sun, 29 Mar 2009, Jan Hubicka wrote:

> Hi,
> bootstrapped/regtested x86_64-linux together with the EHcleanup patches
> using the function. OK?

One nit ...

> 	* bitmap.c (bitmap_last_set_bit): New function.
> 	* bitmap.h (bitmap_last_set_bit): Declare.
> Index: bitmap.c
> ===================================================================
> *** bitmap.c	(revision 145204)
> --- bitmap.c	(working copy)
> *************** bitmap_first_set_bit (const_bitmap a)
> *** 806,811 ****
> --- 806,859 ----
>   #endif
>    return bit_no;
>   }
> + 
> + /* Return the bit number of the first set bit in the bitmap.  The
> +    bitmap must be non-empty.  */
> + 
> + unsigned
> + bitmap_last_set_bit (const_bitmap a)
> + {
> +   const bitmap_element *elt = a->current ? a->current : a->first;
> +   unsigned bit_no;
> +   BITMAP_WORD word;
> +   int ix;
> + 
> +   gcc_assert (elt);
> +   while (elt->next)
> +     elt = elt->next;
> +   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
> +   for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
> +     {
> +       word = elt->bits[ix];
> +       if (word)
> + 	goto found_bit;
> +     }
> +   gcc_unreachable ();
> +  found_bit:
> +   bit_no += ix * BITMAP_WORD_BITS;
> + 
> +   /* Binary search for the last set bit.  */

bitmap_first_set_bit uses __builtin_ctzl if available, I think you
should be able to use __builtin_clzl here.

Ok with that change.

Thanks,
Richard.

> + #if BITMAP_WORD_BITS > 64
> + #error "Fill out the table."
> + #endif
> + #if BITMAP_WORD_BITS > 32
> +   if ((word & 0xffffffff00000000))
> +     word >>= 32, bit_no += 32;
> + #endif
> +   if (word & 0xffff0000)
> +     word >>= 16, bit_no += 16;
> +   if (!(word & 0xff00))
> +     word >>= 8, bit_no += 8;
> +   if (!(word & 0xf0))
> +     word >>= 4, bit_no += 4;
> +   if (!(word & 12))
> +     word >>= 2, bit_no += 2;
> +   if (!(word & 2))
> +     word >>= 1, bit_no += 1;
> + 
> +  gcc_assert (word & 1);
> +  return bit_no;
> + }
>   
>   
>   /* DST = A & B.  */
> Index: bitmap.h
> ===================================================================
> *** bitmap.h	(revision 145204)
> --- bitmap.h	(working copy)
> *************** extern void bitmap_obstack_free (bitmap)
> *** 183,188 ****
> --- 183,189 ----
>   #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
>   #define bitmap_zero(a) bitmap_clear (a)
>   extern unsigned bitmap_first_set_bit (const_bitmap);
> + extern unsigned bitmap_last_set_bit (const_bitmap);
>   
>   /* Compute bitmap hash (for purposes of hashing etc.)  */
>   extern hashval_t bitmap_hash(const_bitmap);
> 
>