PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

This patch was posted on Fri, 28 August 2009.

http://gcc.gnu.org/ml/gcc-patches/2009-08/msg01536.html

Discussed and reviewed with Diego Novillo on the IRC channel.

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

[-- Attachment #1: Type: text/plain, Size: 1860 bytes --]


Nicolas BENOIT wrote:
 > This patch was posted on Fri, 28 August 2009.
 >
 > http://gcc.gnu.org/ml/gcc-patches/2009-08/msg01536.html
 >
 > Discussed and reviewed with Diego Novillo on the IRC channel.
 >

The patch above fixed cache reset in ebitmap_clear_bit() operation.
I discovered another issue with the cache reset, this patch fixes both.

Issue 1 : The map->cacheindex compared against eltwordindex, which is
irrelevant; discussed in the message mentioned above.

Issue 2 : When the cache points to an element which is after the element
being removed, it is not updated, although all the elements are going to
be shifted in the array. Then, the cache points to the succeeding
element it should point to.

This patch fixes both issues :
1/ it uses the correct wordindex to compare cacheindex with.
2/ it makes the cache points one element backwards if the cached
element is about to be shifted.

I attached to this message two testcases for each issue.
The first one is taken from issue 1 initial patch.

By the way, patches

http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00956.html and
http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00959.html

are still pending. I hope someone will have a look at them.

Greetings,
Nicolas BENOIT.


Index: ebitmap.c
===================================================================
--- ebitmap.c	(revision 151856)
+++ ebitmap.c	(working copy)
@@ -254,8 +254,13 @@
        if (!have_eltwordindex)
  	eltwordindex = sbitmap_popcount (map->wordmask, wordindex);

-      if (map->cache != NULL && map->cacheindex == eltwordindex)
-	map->cache = NULL;
+      if (map->cache != NULL)
+        {
+          if (map->cacheindex == wordindex)
+            map->cache = NULL;
+          else if (map->cacheindex > wordindex)
+            map->cache = map->cache - 1;
+        }

        RESET_BIT (map->wordmask, wordindex);



[-- Attachment #2: test-ebitmap_clear_bit-cache_update.c --]
[-- Type: text/plain, Size: 3255 bytes --]


static void
test_ebitmap_clear_bit_cache_update_1 ( void )
{
  ebitmap map1, map2;
  map1 = ebitmap_alloc ( 1 );
  map2 = ebitmap_alloc ( 1 );

  ebitmap_set_bit ( map1, 1247 );
  ebitmap_set_bit ( map1, 1248 );
  ebitmap_set_bit ( map1, 1249 );
  ebitmap_set_bit ( map1, 1250 );
  ebitmap_set_bit ( map1, 1251 );
  ebitmap_set_bit ( map1, 1252 );
  ebitmap_set_bit ( map1, 1293 );
  ebitmap_set_bit ( map1, 1294 );
  ebitmap_set_bit ( map1, 1295 );
  ebitmap_set_bit ( map1, 1296 );
  ebitmap_set_bit ( map1, 1301 );
  ebitmap_set_bit ( map1, 1302 );
  ebitmap_set_bit ( map1, 1303 );
  ebitmap_set_bit ( map1, 1304 );
  ebitmap_set_bit ( map1, 1313 );
  ebitmap_set_bit ( map1, 1314 );
  ebitmap_set_bit ( map1, 1315 );
  ebitmap_set_bit ( map1, 1316 );
  ebitmap_set_bit ( map1, 1317 );
  ebitmap_set_bit ( map1, 1318 );
  ebitmap_set_bit ( map1, 1319 );
  ebitmap_set_bit ( map1, 1320 );
  ebitmap_set_bit ( map2, 1285 );
  ebitmap_clear_bit ( map1, 1285 );
  ebitmap_set_bit ( map2, 1286 );
  ebitmap_clear_bit ( map1, 1286 );
  ebitmap_set_bit ( map2, 1287 );
  ebitmap_clear_bit ( map1, 1287 );
  ebitmap_set_bit ( map2, 1288 );
  ebitmap_clear_bit ( map1, 1288 );
  ebitmap_clear_bit ( map1, 1233 );
  ebitmap_set_bit ( map2, 1234 );
  ebitmap_clear_bit ( map1, 1234 );
  ebitmap_set_bit ( map2, 1235 );
  ebitmap_clear_bit ( map1, 1235 );
  ebitmap_set_bit ( map2, 1236 );
  ebitmap_clear_bit ( map1, 1236 );
  ebitmap_set_bit ( map2, 1237 );
  ebitmap_clear_bit ( map1, 1237 );
  ebitmap_set_bit ( map2, 1238 );
  ebitmap_clear_bit ( map1, 1238 );
  ebitmap_set_bit ( map2, 1239 );
  ebitmap_clear_bit ( map1, 1239 );
  ebitmap_set_bit ( map2, 1240 );
  ebitmap_clear_bit ( map1, 1240 );
  ebitmap_set_bit ( map2, 1245 );
  ebitmap_clear_bit ( map1, 1245 );
  ebitmap_set_bit ( map2, 1246 );
  ebitmap_clear_bit ( map1, 1246 );
  ebitmap_set_bit ( map2, 1247 );
  ebitmap_clear_bit ( map1, 1247 );
  ebitmap_set_bit ( map2, 1248 );
  ebitmap_clear_bit ( map1, 1248 );
  ebitmap_set_bit ( map2, 1249 );
  ebitmap_clear_bit ( map1, 1249 );
  ebitmap_set_bit ( map2, 1250 );
  ebitmap_clear_bit ( map1, 1250 );
  ebitmap_set_bit ( map2, 1251 );
  ebitmap_clear_bit ( map1, 1251 );

  if ( !ebitmap_bit_p(map2,1252) )
    {
      if ( ebitmap_bit_p(map1,1252) )
        {
          ebitmap_set_bit ( map2, 1252 );
          ebitmap_clear_bit ( map1, 1252 );
        }
    }

  gcc_assert ( !ebitmap_bit_p(map1,1253) );

  fprintf ( stderr, "ebitmap_clear_bit() cache update test 1 passed\n" );

  ebitmap_free ( map1 );
  ebitmap_free ( map2 );
}

static void
test_ebitmap_clear_bit_cache_update_2 ( void )
{
  ebitmap map;

  map = ebitmap_alloc ( 1 );
  ebitmap_set_bit ( map, 148 );
  ebitmap_set_bit ( map, 147 );
  ebitmap_set_bit ( map, 146 );
  ebitmap_set_bit ( map, 4026 );
  ebitmap_clear_bit ( map, 146 );
  ebitmap_set_bit ( map, 4040 );
  ebitmap_clear_bit ( map, 147 );
  ebitmap_set_bit ( map, 4054 );
  ebitmap_clear_bit ( map, 148 );
  gcc_assert ( !ebitmap_bit_p(map,4032) );

  fprintf ( stderr, "ebitmap_clear_bit() cache update test 2 passed\n" );

  ebitmap_free ( map );
}

static void
test_ebitmap_clear_bit_cache_update ( void )
{
  test_ebitmap_clear_bit_cache_update_1 ( );
  test_ebitmap_clear_bit_cache_update_2 ( );
}

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Ian Lance Taylor]

Nicolas BENOIT <nbenoit@tuxfamily.org> writes:

> I discovered another issue with the cache reset, this patch fixes both.
>
> Issue 1 : The map->cacheindex compared against eltwordindex, which is
> irrelevant; discussed in the message mentioned above.
>
> Issue 2 : When the cache points to an element which is after the element
> being removed, it is not updated, although all the elements are going to
> be shifted in the array. Then, the cache points to the succeeding
> element it should point to.
>
> This patch fixes both issues :
> 1/ it uses the correct wordindex to compare cacheindex with.
> 2/ it makes the cache points one element backwards if the cached
> element is about to be shifted.
>
> I attached to this message two testcases for each issue.
> The first one is taken from issue 1 initial patch.
>
> By the way, patches
>
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00956.html and
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00959.html
>
> are still pending. I hope someone will have a look at them.

This patch is OK with a ChangeLog entry.

Thanks.

Ian

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

Ian Lance Taylor wrote:
> Nicolas BENOIT <nbenoit@tuxfamily.org> writes:
> 
>> I discovered another issue with the cache reset, this patch fixes both.
>>
>> Issue 1 : The map->cacheindex compared against eltwordindex, which is
>> irrelevant; discussed in the message mentioned above.
>>
>> Issue 2 : When the cache points to an element which is after the element
>> being removed, it is not updated, although all the elements are going to
>> be shifted in the array. Then, the cache points to the succeeding
>> element it should point to.
>>
>> This patch fixes both issues :
>> 1/ it uses the correct wordindex to compare cacheindex with.
>> 2/ it makes the cache points one element backwards if the cached
>> element is about to be shifted.
>>
>> I attached to this message two testcases for each issue.
>> The first one is taken from issue 1 initial patch.
>>
>> By the way, patches
>>
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00956.html and
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00959.html
>>
>> are still pending. I hope someone will have a look at them.
> 
> This patch is OK with a ChangeLog entry.
> 
> Thanks.
> 
> Ian
> 

Hi,

Here is a proposition for the ChangeLog entry :

2009-09-22  Nicolas Benoit  <nbenoit@tuxfamily.org>

	* ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test and
	map>cache update when bit clearing results to an empty element.


I don't know wether the date should correspond to the patch proposal or 
to the commit date, I let you update it if needed.

Regards,
Nicolas.

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Ian Lance Taylor]

Nicolas BENOIT <nbenoit@tuxfamily.org> writes:

> Here is a proposition for the ChangeLog entry :
>
> 2009-09-22  Nicolas Benoit  <nbenoit@tuxfamily.org>
>
> 	* ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test and
> 	map>cache update when bit clearing results to an empty element.
>
>
> I don't know wether the date should correspond to the patch proposal
> or to the commit date, I let you update it if needed.

It should correspond to the commit date.  Whoever commits the patch
will normally correct that date.

Looking for volunteers to commit Nicolas's patches....

Ian

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

Ian Lance Taylor wrote:
> Nicolas BENOIT <nbenoit@tuxfamily.org> writes:
> 
>> Here is a proposition for the ChangeLog entry :
>>
>> 2009-09-22  Nicolas Benoit  <nbenoit@tuxfamily.org>
>>
>> 	* ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test and
>> 	map>cache update when bit clearing results to an empty element.
>>
>>
>> I don't know wether the date should correspond to the patch proposal
>> or to the commit date, I let you update it if needed.
> 
> It should correspond to the commit date.  Whoever commits the patch
> will normally correct that date.
> 
> Looking for volunteers to commit Nicolas's patches....
 >
 > Ian
 >


Hi,

Patches

http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html

are still pending. The ChangeLog for the second one is above.

Greetings,
Nicolas.

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

Nicolas BENOIT wrote:
> Ian Lance Taylor wrote:
>> Nicolas BENOIT <nbenoit@tuxfamily.org> writes:
>>
>>> Here is a proposition for the ChangeLog entry :
>>>
>>> 2009-09-22  Nicolas Benoit  <nbenoit@tuxfamily.org>
>>>
>>>     * ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test and
>>>     map>cache update when bit clearing results to an empty element.
>>>
>>>
>>> I don't know wether the date should correspond to the patch proposal
>>> or to the commit date, I let you update it if needed.
>>
>> It should correspond to the commit date.  Whoever commits the patch
>> will normally correct that date.
>>
>> Looking for volunteers to commit Nicolas's patches....
>  >
>  > Ian
>  >
> 
> 
> Hi,
> 
> Patches
> 
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
> 
> are still pending. The ChangeLog for the second one is above.
> 
> Greetings,
> Nicolas.
> 

Hi,

The two patches mentioned above are still waiting for commit.

Regards,
Nicolas.

PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

Hi all,

A while ago, I submitted a few patches for ebitmap.

Two of them have been validated and are still waiting for commit.

http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html


Greetings,
Nicolas.


On 10/29/2009 06:35 PM, Nicolas BENOIT wrote:
> Nicolas BENOIT wrote:
>> Ian Lance Taylor wrote:
>>> Nicolas BENOIT <nbenoit@tuxfamily.org> writes:
>>>
>>>> Here is a proposition for the ChangeLog entry :
>>>>
>>>> 2009-09-22 Nicolas Benoit <nbenoit@tuxfamily.org>
>>>>
>>>> * ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test and
>>>> map>cache update when bit clearing results to an empty element.
>>>>
>>>>
>>>> I don't know wether the date should correspond to the patch proposal
>>>> or to the commit date, I let you update it if needed.
>>>
>>> It should correspond to the commit date. Whoever commits the patch
>>> will normally correct that date.
>>>
>>> Looking for volunteers to commit Nicolas's patches....
>> >
>> > Ian
>> >
>>
>>
>> Hi,
>>
>> Patches
>>
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
>>
>> are still pending. The ChangeLog for the second one is above.
>>
>> Greetings,
>> Nicolas.
>>
>
> Hi,
>
> The two patches mentioned above are still waiting for commit.
>
> Regards,
> Nicolas.
>

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Diego Novillo]

On Wed, Feb 24, 2010 at 13:32, Nicolas BENOIT <nbenoit@tuxfamily.org> wrote:
> Hi all,
>
> A while ago, I submitted a few patches for ebitmap.
>
> Two of them have been validated and are still waiting for commit.
>
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html

I will commit them for you.  RMs, is this OK at this stage?  The
patches were approved long ago, but fell through the cracks for the
final commit.


Thanks.  Diego.

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Mark Mitchell]

Diego Novillo wrote:

>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
> 
> I will commit them for you.  RMs, is this OK at this stage?  The
> patches were approved long ago, but fell through the cracks for the
> final commit.

This is OK.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT]

On 02/24/2010 09:26 PM, Diego Novillo wrote:
> On Wed, Feb 24, 2010 at 13:32, Nicolas BENOIT<nbenoit@tuxfamily.org>  wrote:
>> Hi all,
>>
>> A while ago, I submitted a few patches for ebitmap.
>>
>> Two of them have been validated and are still waiting for commit.
>>
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
>
> I will commit them for you.  RMs, is this OK at this stage?  The
> patches were approved long ago, but fell through the cracks for the
> final commit.
>
>
> Thanks.  Diego.
>

Patch http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
is not applying to trunk since the big whitespace removal, here is an 
updated version :


Index: ebitmap.c
===================================================================
--- ebitmap.c	(revision 157065)
+++ ebitmap.c	(working copy)
@@ -254,8 +254,13 @@
        if (!have_eltwordindex)
  	eltwordindex = sbitmap_popcount (map->wordmask, wordindex);

-      if (map->cache != NULL && map->cacheindex == eltwordindex)
-	map->cache = NULL;
+      if (map->cache != NULL)
+        {
+          if (map->cacheindex == wordindex)
+            map->cache = NULL;
+          else if (map->cacheindex > wordindex)
+            map->cache = map->cache - 1;
+        }

        RESET_BIT (map->wordmask, wordindex);

Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Diego Novillo]

[-- Attachment #1: Type: text/plain, Size: 508 bytes --]

On Wed, Feb 24, 2010 at 15:32, Mark Mitchell <mark@codesourcery.com> wrote:
> Diego Novillo wrote:
>
>>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01921.html
>>> http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01547.html
>>
>> I will commit them for you.  RMs, is this OK at this stage?  The
>> patches were approved long ago, but fell through the cracks for the
>> final commit.
>
> This is OK.

Bootstrapped and tested on all x86_64 for all languages.  Committed as
rev 157080.


Diego.

[-- Attachment #2: 20100225-ebitmap.diff.txt --]
[-- Type: text/plain, Size: 3370 bytes --]

2010-02-25  Nicolas Benoit  <nbenoit@tuxfamily.org>

	* ebitmap.c: Change calls to verify_popcount with calls to
	sbitmap_verify_popcount.
	(ebitmap_clear_bit): Fixed map->cacheindex test and
	map>cache update when bit clearing results in an empty
	element.

Index: ebitmap.c
===================================================================
--- ebitmap.c	(revision 157079)
+++ ebitmap.c	(working copy)
@@ -1,5 +1,5 @@
 /* Sparse array-based bitmaps.
-   Copyright (C) 2007, 2008 Free Software Foundation, Inc.
+   Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
    Contributed by Daniel Berlin <dberlin@dberlin.org>
 
 This file is part of GCC.
@@ -254,8 +254,13 @@ ebitmap_clear_bit (ebitmap map, unsigned
       if (!have_eltwordindex)
 	eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
 
-      if (map->cache != NULL && map->cacheindex == eltwordindex)
-	map->cache = NULL;
+      if (map->cache != NULL)
+        {
+          if (map->cacheindex == wordindex)
+            map->cache = NULL;
+          else if (map->cacheindex > wordindex)
+            map->cache = map->cache - 1;
+        }
 
       RESET_BIT (map->wordmask, wordindex);
 
@@ -457,7 +462,7 @@ ebitmap_and_into (ebitmap dst, ebitmap s
     for (i = 0; i <  dst->numwords; i++)
       gcc_assert (dst->elts[i] != 0);
 
-    verify_popcount (dst->wordmask);
+    sbitmap_verify_popcount (dst->wordmask);
     gcc_assert (sbitmap_popcount (dst->wordmask,
 				  dst->wordmask->n_bits) == dst->numwords);
   }
@@ -529,7 +534,7 @@ ebitmap_and (ebitmap dst, ebitmap src1, 
     for (i = 0; i <  dst->numwords; i++)
       gcc_assert (dst->elts[i] != 0);
 
-    verify_popcount (dst->wordmask);
+    sbitmap_verify_popcount (dst->wordmask);
     gcc_assert (sbitmap_popcount (dst->wordmask,
 				  dst->wordmask->n_bits) == dst->numwords);
   }
@@ -652,7 +657,7 @@ ebitmap_ior_into (ebitmap dst, ebitmap s
     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
       gcc_assert (ebitmap_bit_p (dst, i));
 
-    verify_popcount (dst->wordmask);
+    sbitmap_verify_popcount (dst->wordmask);
     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
     gcc_assert (sbitmap_popcount (dst->wordmask,
 				  dst->wordmask->n_bits) == dst->numwords);
@@ -772,7 +777,7 @@ ebitmap_ior (ebitmap dst, ebitmap src1, 
     EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
       gcc_assert (ebitmap_bit_p (dst, i));
   }
-  verify_popcount (dst->wordmask);
+  sbitmap_verify_popcount (dst->wordmask);
   gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
   gcc_assert (sbitmap_popcount (dst->wordmask,
 				dst->wordmask->n_bits) == dst->numwords);
@@ -848,7 +853,7 @@ ebitmap_and_compl_into (ebitmap dst, ebi
 
     gcc_assert (sbitmap_popcount (dst->wordmask,
 				  dst->wordmask->n_bits) == neweltindex);
-    verify_popcount (dst->wordmask);
+    sbitmap_verify_popcount (dst->wordmask);
     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
     gcc_assert (sbitmap_popcount (dst->wordmask,
 				  dst->wordmask->n_bits) == dst->numwords);
@@ -950,7 +955,7 @@ ebitmap_and_compl (ebitmap dst, ebitmap 
   for (i = 0; i <  dst->numwords; i++)
     gcc_assert (dst->elts[i] != 0);
 
-  verify_popcount (dst->wordmask);
+  sbitmap_verify_popcount (dst->wordmask);
   gcc_assert (sbitmap_popcount (dst->wordmask,
 				dst->wordmask->n_bits) == dst->numwords);
   }