Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/13/2017 07:02 AM, Martin Liška wrote:
> On 10/12/2017 11:54 PM, Jeff Law wrote:
>> On 10/11/2017 12:13 AM, Martin Liška wrote:
>>> 2017-10-10 Martin Liska
>>>
>>> PR tree-optimization/82493
>>> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
>>> (test_range_functions): New function.
>>> (sbitmap_c_tests): Likewise.
>>> * selftest-run-tests.c (selftest::run_tests): Run new tests.
>>> * selftest.h (sbitmap_c_tests): New function.
>> I went ahead and committed this along with a patch to fix the off-by-one
>> error in live_bytes_read. Bootstrapped and regression tested on x86.
>>
>> Actual patch attached for archival purposes.
>>
>> Jeff
>>
> Hello.
>
> I wrote a patch that adds various gcc_checking_asserts and I hit following:
>
> ./xgcc -B.
> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90 -c
> -O2
> during GIMPLE pass: dse
> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90:7:0:
>
> program testat
>
> internal compiler error: in bitmap_check_index, at sbitmap.h:105
> 0x1c014c1 bitmap_check_index
> ../../gcc/sbitmap.h:105
> 0x1c01fa7 bitmap_bit_in_range_p(simple_bitmap_def const*, unsigned int,
> unsigned int)
> ../../gcc/sbitmap.c:335
> 0x1179002 live_bytes_read
> ../../gcc/tree-ssa-dse.c:497
> 0x117935a dse_classify_store
> ../../gcc/tree-ssa-dse.c:595
> 0x1179947 dse_dom_walker::dse_optimize_stmt(gimple_stmt_iterator*)
> ../../gcc/tree-ssa-dse.c:786
> 0x1179b6e dse_dom_walker::before_dom_children(basic_block_def*)
> ../../gcc/tree-ssa-dse.c:853
> 0x1a6f659 dom_walker::walk(basic_block_def*)
> ../../gcc/domwalk.c:308
> 0x1179cb9 execute
> ../../gcc/tree-ssa-dse.c:907
>
> Where we call:
> Breakpoint 1, bitmap_bit_in_range_p (bmap=0x29d6cd0, start=0, end=515) at
> ../../gcc/sbitmap.c:335
> 335 bitmap_check_index (bmap, end);
> (gdb) p *bmap
> $1 = {n_bits = 256, size = 4, elms = {255}}
>
> Is it a valid call or should caller check indices?
>
> Martin
>
>
> 0002-Add-gcc_checking_assert-for-sbitmap.c.patch
>
>
> From ba3d597be70b8329abafe92da868ab5250610840 Mon Sep 17 00:00:00 2001
> From: marxin
> Date: Fri, 13 Oct 2017 13:39:08 +0200
> Subject: [PATCH 2/2] Add gcc_checking_assert for sbitmap.c.
>
> ---
> gcc/sbitmap.c | 39 +++
> gcc/sbitmap.h | 25 +
> 2 files changed, 64 insertions(+)
So the only change that concerned me was the bitmap_subset_p test. In
theory they don't need to be the same size for that test. However, I
think we should go ahead with your patch as-is and deal with that
possibility if and when we need the capability to do a subset test with
different sized bitmaps.
jeff
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/16/2017 06:03 AM, Martin Liška wrote:
> On 10/13/2017 04:59 PM, Jeff Law wrote:
>> On 10/13/2017 07:02 AM, Martin Liška wrote:
>>> On 10/12/2017 11:54 PM, Jeff Law wrote:
On 10/11/2017 12:13 AM, Martin Liška wrote:
> 2017-10-10 Martin Liska
>
> PR tree-optimization/82493
> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
> (test_range_functions): New function.
> (sbitmap_c_tests): Likewise.
> * selftest-run-tests.c (selftest::run_tests): Run new tests.
> * selftest.h (sbitmap_c_tests): New function.
I went ahead and committed this along with a patch to fix the off-by-one
error in live_bytes_read. Bootstrapped and regression tested on x86.
Actual patch attached for archival purposes.
Jeff
>>>
>>> Hello.
>>>
>>> I wrote a patch that adds various gcc_checking_asserts and I hit following:
>>>
>>> ./xgcc -B.
>>> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90
>>> -c -O2
>>> during GIMPLE pass: dse
>>> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90:7:0:
>>>
>>> program testat
>>>
>>> internal compiler error: in bitmap_check_index, at sbitmap.h:105
>>> 0x1c014c1 bitmap_check_index
>>> ../../gcc/sbitmap.h:105
>>> 0x1c01fa7 bitmap_bit_in_range_p(simple_bitmap_def const*, unsigned int,
>>> unsigned int)
>>> ../../gcc/sbitmap.c:335
>>> 0x1179002 live_bytes_read
>>> ../../gcc/tree-ssa-dse.c:497
>>> 0x117935a dse_classify_store
>>> ../../gcc/tree-ssa-dse.c:595
>>> 0x1179947 dse_dom_walker::dse_optimize_stmt(gimple_stmt_iterator*)
>>> ../../gcc/tree-ssa-dse.c:786
>>> 0x1179b6e dse_dom_walker::before_dom_children(basic_block_def*)
>>> ../../gcc/tree-ssa-dse.c:853
>>> 0x1a6f659 dom_walker::walk(basic_block_def*)
>>> ../../gcc/domwalk.c:308
>>> 0x1179cb9 execute
>>> ../../gcc/tree-ssa-dse.c:907
>>>
>>> Where we call:
>>> Breakpoint 1, bitmap_bit_in_range_p (bmap=0x29d6cd0, start=0, end=515) at
>>> ../../gcc/sbitmap.c:335
>>> 335 bitmap_check_index (bmap, end);
>>> (gdb) p *bmap
>>> $1 = {n_bits = 256, size = 4, elms = {255}}
>>>
>>> Is it a valid call or should caller check indices?
>> It doesn't look valid to me. I'll dig into it.
>>
>> In general the sbitmap interface requires callers to DTRT -- failure can
>> easily lead to an out of bounds read or write. It's one of the things I
>> really dislike about the sbitmap implementation.
>>
>> So it's safe to assume that I'm fully supportive of adding more testing
>> to catch this kind thing.
>>
>> Jeff
>>
>
> Good.
>
> Should I prepare fix for the ICE I mentioned or have you been working on that?
I've already got a patch for it. I'll likely commit it this morning.
jeff
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/13/2017 04:59 PM, Jeff Law wrote:
> On 10/13/2017 07:02 AM, Martin Liška wrote:
>> On 10/12/2017 11:54 PM, Jeff Law wrote:
>>> On 10/11/2017 12:13 AM, Martin Liška wrote:
2017-10-10 Martin Liska
PR tree-optimization/82493
* sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
(test_range_functions): New function.
(sbitmap_c_tests): Likewise.
* selftest-run-tests.c (selftest::run_tests): Run new tests.
* selftest.h (sbitmap_c_tests): New function.
>>> I went ahead and committed this along with a patch to fix the off-by-one
>>> error in live_bytes_read. Bootstrapped and regression tested on x86.
>>>
>>> Actual patch attached for archival purposes.
>>>
>>> Jeff
>>>
>>
>> Hello.
>>
>> I wrote a patch that adds various gcc_checking_asserts and I hit following:
>>
>> ./xgcc -B.
>> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90 -c
>> -O2
>> during GIMPLE pass: dse
>> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90:7:0:
>>
>> program testat
>>
>> internal compiler error: in bitmap_check_index, at sbitmap.h:105
>> 0x1c014c1 bitmap_check_index
>> ../../gcc/sbitmap.h:105
>> 0x1c01fa7 bitmap_bit_in_range_p(simple_bitmap_def const*, unsigned int,
>> unsigned int)
>> ../../gcc/sbitmap.c:335
>> 0x1179002 live_bytes_read
>> ../../gcc/tree-ssa-dse.c:497
>> 0x117935a dse_classify_store
>> ../../gcc/tree-ssa-dse.c:595
>> 0x1179947 dse_dom_walker::dse_optimize_stmt(gimple_stmt_iterator*)
>> ../../gcc/tree-ssa-dse.c:786
>> 0x1179b6e dse_dom_walker::before_dom_children(basic_block_def*)
>> ../../gcc/tree-ssa-dse.c:853
>> 0x1a6f659 dom_walker::walk(basic_block_def*)
>> ../../gcc/domwalk.c:308
>> 0x1179cb9 execute
>> ../../gcc/tree-ssa-dse.c:907
>>
>> Where we call:
>> Breakpoint 1, bitmap_bit_in_range_p (bmap=0x29d6cd0, start=0, end=515) at
>> ../../gcc/sbitmap.c:335
>> 335bitmap_check_index (bmap, end);
>> (gdb) p *bmap
>> $1 = {n_bits = 256, size = 4, elms = {255}}
>>
>> Is it a valid call or should caller check indices?
> It doesn't look valid to me. I'll dig into it.
>
> In general the sbitmap interface requires callers to DTRT -- failure can
> easily lead to an out of bounds read or write. It's one of the things I
> really dislike about the sbitmap implementation.
>
> So it's safe to assume that I'm fully supportive of adding more testing
> to catch this kind thing.
>
> Jeff
>
Good.
Should I prepare fix for the ICE I mentioned or have you been working on that?
Thanks,
Martin
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/13/2017 07:02 AM, Martin Liška wrote:
> On 10/12/2017 11:54 PM, Jeff Law wrote:
>> On 10/11/2017 12:13 AM, Martin Liška wrote:
>>> 2017-10-10 Martin Liska
>>>
>>> PR tree-optimization/82493
>>> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
>>> (test_range_functions): New function.
>>> (sbitmap_c_tests): Likewise.
>>> * selftest-run-tests.c (selftest::run_tests): Run new tests.
>>> * selftest.h (sbitmap_c_tests): New function.
>> I went ahead and committed this along with a patch to fix the off-by-one
>> error in live_bytes_read. Bootstrapped and regression tested on x86.
>>
>> Actual patch attached for archival purposes.
>>
>> Jeff
>>
>
> Hello.
>
> I wrote a patch that adds various gcc_checking_asserts and I hit following:
>
> ./xgcc -B.
> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90 -c
> -O2
> during GIMPLE pass: dse
> /home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90:7:0:
>
> program testat
>
> internal compiler error: in bitmap_check_index, at sbitmap.h:105
> 0x1c014c1 bitmap_check_index
> ../../gcc/sbitmap.h:105
> 0x1c01fa7 bitmap_bit_in_range_p(simple_bitmap_def const*, unsigned int,
> unsigned int)
> ../../gcc/sbitmap.c:335
> 0x1179002 live_bytes_read
> ../../gcc/tree-ssa-dse.c:497
> 0x117935a dse_classify_store
> ../../gcc/tree-ssa-dse.c:595
> 0x1179947 dse_dom_walker::dse_optimize_stmt(gimple_stmt_iterator*)
> ../../gcc/tree-ssa-dse.c:786
> 0x1179b6e dse_dom_walker::before_dom_children(basic_block_def*)
> ../../gcc/tree-ssa-dse.c:853
> 0x1a6f659 dom_walker::walk(basic_block_def*)
> ../../gcc/domwalk.c:308
> 0x1179cb9 execute
> ../../gcc/tree-ssa-dse.c:907
>
> Where we call:
> Breakpoint 1, bitmap_bit_in_range_p (bmap=0x29d6cd0, start=0, end=515) at
> ../../gcc/sbitmap.c:335
> 335 bitmap_check_index (bmap, end);
> (gdb) p *bmap
> $1 = {n_bits = 256, size = 4, elms = {255}}
>
> Is it a valid call or should caller check indices?
It doesn't look valid to me. I'll dig into it.
In general the sbitmap interface requires callers to DTRT -- failure can
easily lead to an out of bounds read or write. It's one of the things I
really dislike about the sbitmap implementation.
So it's safe to assume that I'm fully supportive of adding more testing
to catch this kind thing.
Jeff
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/13/2017 07:03 AM, Martin Liška wrote: > On 10/13/2017 10:01 AM, Martin Liška wrote: >> On 10/12/2017 11:54 PM, Jeff Law wrote: >>> On 10/11/2017 12:13 AM, Martin Liška wrote: 2017-10-10 Martin Liska PR tree-optimization/82493 * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation. (test_range_functions): New function. (sbitmap_c_tests): Likewise. * selftest-run-tests.c (selftest::run_tests): Run new tests. * selftest.h (sbitmap_c_tests): New function. >>> I went ahead and committed this along with a patch to fix the off-by-one >>> error in live_bytes_read. Bootstrapped and regression tested on x86. >>> >>> Actual patch attached for archival purposes. >>> >>> Jeff >>> >> >> Thanks. >> >> I'll carry on and write another set of unit tests. >> >> Martin >> > > Sending patch candidate, may I install it after it finishes regression tests? Yes. Please. Jeff
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/13/2017 10:01 AM, Martin Liška wrote:
> On 10/12/2017 11:54 PM, Jeff Law wrote:
>> On 10/11/2017 12:13 AM, Martin Liška wrote:
>>> 2017-10-10 Martin Liska
>>>
>>> PR tree-optimization/82493
>>> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
>>> (test_range_functions): New function.
>>> (sbitmap_c_tests): Likewise.
>>> * selftest-run-tests.c (selftest::run_tests): Run new tests.
>>> * selftest.h (sbitmap_c_tests): New function.
>> I went ahead and committed this along with a patch to fix the off-by-one
>> error in live_bytes_read. Bootstrapped and regression tested on x86.
>>
>> Actual patch attached for archival purposes.
>>
>> Jeff
>>
>
> Thanks.
>
> I'll carry on and write another set of unit tests.
>
> Martin
>
Sending patch candidate, may I install it after it finishes regression tests?
Martin
>From 6114004455ffc534cdb895eb74b2018cea4b704a Mon Sep 17 00:00:00 2001
From: marxin
Date: Fri, 13 Oct 2017 13:18:47 +0200
Subject: [PATCH 1/2] Add selftests for bitmap_set_range.
gcc/ChangeLog:
2017-10-13 Martin Liska
* sbitmap.c (bitmap_bit_in_range_p_checking): New function.
(test_set_range): Likewise.
(test_range_functions): Rename to ...
(test_bit_in_range): ... this.
(sbitmap_c_tests): Add new test.
---
gcc/sbitmap.c | 60 ---
1 file changed, 57 insertions(+), 3 deletions(-)
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index baef4d05f0d..fdcf5393e53 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -823,11 +823,64 @@ namespace selftest {
/* Selftests for sbitmaps. */
+/* Checking function that uses both bitmap_bit_in_range_p and
+ loop of bitmap_bit_p and verifies consistent results. */
-/* Verify range functions for sbitmap. */
+static bool
+bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
+unsigned end)
+{
+ bool r1 = bitmap_bit_in_range_p (s, start, end);
+ bool r2 = false;
+
+ for (unsigned int i = start; i <= end; i++)
+if (bitmap_bit_p (s, i))
+ {
+ r2 = true;
+ break;
+ }
+
+ ASSERT_EQ (r1, r2);
+ return r1;
+}
+
+/* Verify bitmap_set_range functions for sbitmap. */
+
+static void
+test_set_range ()
+{
+ sbitmap s = sbitmap_alloc (16);
+ bitmap_clear (s);
+
+ bitmap_set_range (s, 0, 1);
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
+ bitmap_set_range (s, 15, 1);
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
+
+ s = sbitmap_alloc (1024);
+ bitmap_clear (s);
+ bitmap_set_range (s, 512, 1);
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
+
+ bitmap_clear (s);
+ bitmap_set_range (s, 512, 64);
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
+ ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
+ ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
+}
+
+/* Verify bitmap_bit_in_range_p functions for sbitmap. */
static void
-test_range_functions ()
+test_bit_in_range ()
{
sbitmap s = sbitmap_alloc (1024);
bitmap_clear (s);
@@ -900,7 +953,8 @@ test_range_functions ()
void
sbitmap_c_tests ()
{
- test_range_functions ();
+ test_set_range ();
+ test_bit_in_range ();
}
} // namespace selftest
--
2.14.2
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/12/2017 11:54 PM, Jeff Law wrote:
> On 10/11/2017 12:13 AM, Martin Liška wrote:
>> 2017-10-10 Martin Liska
>>
>> PR tree-optimization/82493
>> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
>> (test_range_functions): New function.
>> (sbitmap_c_tests): Likewise.
>> * selftest-run-tests.c (selftest::run_tests): Run new tests.
>> * selftest.h (sbitmap_c_tests): New function.
> I went ahead and committed this along with a patch to fix the off-by-one
> error in live_bytes_read. Bootstrapped and regression tested on x86.
>
> Actual patch attached for archival purposes.
>
> Jeff
>
Hello.
I wrote a patch that adds various gcc_checking_asserts and I hit following:
./xgcc -B.
/home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90 -c -O2
during GIMPLE pass: dse
/home/marxin/Programming/gcc/gcc/testsuite/gfortran.dg/char_result_12.f90:7:0:
program testat
internal compiler error: in bitmap_check_index, at sbitmap.h:105
0x1c014c1 bitmap_check_index
../../gcc/sbitmap.h:105
0x1c01fa7 bitmap_bit_in_range_p(simple_bitmap_def const*, unsigned int,
unsigned int)
../../gcc/sbitmap.c:335
0x1179002 live_bytes_read
../../gcc/tree-ssa-dse.c:497
0x117935a dse_classify_store
../../gcc/tree-ssa-dse.c:595
0x1179947 dse_dom_walker::dse_optimize_stmt(gimple_stmt_iterator*)
../../gcc/tree-ssa-dse.c:786
0x1179b6e dse_dom_walker::before_dom_children(basic_block_def*)
../../gcc/tree-ssa-dse.c:853
0x1a6f659 dom_walker::walk(basic_block_def*)
../../gcc/domwalk.c:308
0x1179cb9 execute
../../gcc/tree-ssa-dse.c:907
Where we call:
Breakpoint 1, bitmap_bit_in_range_p (bmap=0x29d6cd0, start=0, end=515) at
../../gcc/sbitmap.c:335
335 bitmap_check_index (bmap, end);
(gdb) p *bmap
$1 = {n_bits = 256, size = 4, elms = {255}}
Is it a valid call or should caller check indices?
Martin
>From ba3d597be70b8329abafe92da868ab5250610840 Mon Sep 17 00:00:00 2001
From: marxin
Date: Fri, 13 Oct 2017 13:39:08 +0200
Subject: [PATCH 2/2] Add gcc_checking_assert for sbitmap.c.
---
gcc/sbitmap.c | 39 +++
gcc/sbitmap.h | 25 +
2 files changed, 64 insertions(+)
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index fdcf5393e53..df933f6516c 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -180,6 +180,8 @@ sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
void
bitmap_copy (sbitmap dst, const_sbitmap src)
{
+ gcc_checking_assert (src->size <= dst->size);
+
memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
}
@@ -187,6 +189,8 @@ bitmap_copy (sbitmap dst, const_sbitmap src)
int
bitmap_equal_p (const_sbitmap a, const_sbitmap b)
{
+ bitmap_check_sizes (a, b);
+
return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
}
@@ -211,6 +215,8 @@ bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
if (count == 0)
return;
+ bitmap_check_index (bmap, start + count - 1);
+
unsigned int start_word = start / SBITMAP_ELT_BITS;
unsigned int start_bitno = start % SBITMAP_ELT_BITS;
@@ -267,6 +273,8 @@ bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
if (count == 0)
return;
+ bitmap_check_index (bmap, start + count - 1);
+
unsigned int start_word = start / SBITMAP_ELT_BITS;
unsigned int start_bitno = start % SBITMAP_ELT_BITS;
@@ -324,6 +332,8 @@ bool
bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
{
gcc_checking_assert (start <= end);
+ bitmap_check_index (bmap, end);
+
unsigned int start_word = start / SBITMAP_ELT_BITS;
unsigned int start_bitno = start % SBITMAP_ELT_BITS;
@@ -467,6 +477,9 @@ bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
bool
bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
{
+ bitmap_check_sizes (a, b);
+ bitmap_check_sizes (b, c);
+
unsigned int i, n = dst->size;
sbitmap_ptr dstp = dst->elms;
const_sbitmap_ptr ap = a->elms;
@@ -489,6 +502,8 @@ bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitm
void
bitmap_not (sbitmap dst, const_sbitmap src)
{
+ bitmap_check_sizes (src, dst);
+
unsigned int i, n = dst->size;
sbitmap_ptr dstp = dst->elms;
const_sbitmap_ptr srcp = src->elms;
@@ -510,6 +525,9 @@ bitmap_not (sbitmap dst, const_sbitmap src)
void
bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
{
+ bitmap_check_sizes (a, b);
+ bitmap_check_sizes (b, dst);
+
unsigned int i, dst_size = dst->size;
unsigned int min_size = dst->size;
sbitmap_ptr dstp = dst->elms;
@@ -537,6 +555,8 @@ bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
bool
bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
{
+ bitmap_check_sizes (a, b);
+
const_sbitmap_ptr ap = a->elms;
const_sbitmap_ptr bp = b->elms;
unsigned int i, n;
@@ -555,6 +575
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/12/2017 11:54 PM, Jeff Law wrote: > On 10/11/2017 12:13 AM, Martin Liška wrote: >> 2017-10-10 Martin Liska >> >> PR tree-optimization/82493 >> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation. >> (test_range_functions): New function. >> (sbitmap_c_tests): Likewise. >> * selftest-run-tests.c (selftest::run_tests): Run new tests. >> * selftest.h (sbitmap_c_tests): New function. > I went ahead and committed this along with a patch to fix the off-by-one > error in live_bytes_read. Bootstrapped and regression tested on x86. > > Actual patch attached for archival purposes. > > Jeff > Thanks. I'll carry on and write another set of unit tests. Martin
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/11/2017 12:13 AM, Martin Liška wrote:
> 2017-10-10 Martin Liska
>
> PR tree-optimization/82493
> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
> (test_range_functions): New function.
> (sbitmap_c_tests): Likewise.
> * selftest-run-tests.c (selftest::run_tests): Run new tests.
> * selftest.h (sbitmap_c_tests): New function.
I went ahead and committed this along with a patch to fix the off-by-one
error in live_bytes_read. Bootstrapped and regression tested on x86.
Actual patch attached for archival purposes.
Jeff
commit 00112593cb12ac28e78c33a0aaeebd91a09f3826
Author: law
Date: Thu Oct 12 21:53:21 2017 +
PR tree-optimization/82493
* sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
(test_range_functions): New function.
(sbitmap_c_tests): Likewise.
* selftest-run-tests.c (selftest::run_tests): Run new tests.
* selftest.h (sbitmap_c_tests): New function.
* tree-ssa-dse.c (live_bytes_read): Fix thinko.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@253699
138bc75d-0d04-0410-961f-82ee72b054a4
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 20fb303d03a..b5981edddc4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2017-10-12 Martin Liska
+
+ PR tree-optimization/82493
+ * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
+ (test_range_functions): New function.
+ (sbitmap_c_tests): Likewise.
+ * selftest-run-tests.c (selftest::run_tests): Run new tests.
+ * selftest.h (sbitmap_c_tests): New function.
+
+ * tree-ssa-dse.c (live_bytes_read): Fix thinko.
+
2017-10-12 Michael Meissner
* config/rs6000/amo.h: Fix spacing issue.
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index 4bf13a11a1d..baef4d05f0d 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see
#include "system.h"
#include "coretypes.h"
#include "sbitmap.h"
+#include "selftest.h"
typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
@@ -322,29 +323,22 @@ bitmap_set_range (sbitmap bmap, unsigned int start,
unsigned int count)
bool
bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int
end)
{
+ gcc_checking_assert (start <= end);
unsigned int start_word = start / SBITMAP_ELT_BITS;
unsigned int start_bitno = start % SBITMAP_ELT_BITS;
- /* Testing within a word, starting at the beginning of a word. */
- if (start_bitno == 0 && (end - start) < SBITMAP_ELT_BITS)
-{
- SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << (end - start)) - 1;
- return (bmap->elms[start_word] & mask) != 0;
-}
-
unsigned int end_word = end / SBITMAP_ELT_BITS;
unsigned int end_bitno = end % SBITMAP_ELT_BITS;
- /* Testing starts somewhere in the middle of a word. Test up to the
- end of the word or the end of the requested region, whichever comes
- first. */
+ /* Check beginning of first word if different from zero. */
if (start_bitno != 0)
{
- unsigned int nbits = ((start_word == end_word)
- ? end_bitno - start_bitno
- : SBITMAP_ELT_BITS - start_bitno);
- SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
- mask <<= start_bitno;
+ SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
+ if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
+ high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
+
+ SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
+ SBITMAP_ELT_TYPE mask = high_mask - low_mask;
if (bmap->elms[start_word] & mask)
return true;
start_word++;
@@ -364,8 +358,9 @@ bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int
start, unsigned int end)
}
/* Now handle residuals in the last word. */
- SBITMAP_ELT_TYPE mask
-= ((SBITMAP_ELT_TYPE)1 << (SBITMAP_ELT_BITS - end_bitno)) - 1;
+ SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
+ if (end_bitno + 1 < SBITMAP_ELT_BITS)
+mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
return (bmap->elms[start_word] & mask) != 0;
}
@@ -821,3 +816,92 @@ dump_bitmap_vector (FILE *file, const char *title, const
char *subtitle,
fprintf (file, "\n");
}
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Selftests for sbitmaps. */
+
+
+/* Verify range functions for sbitmap. */
+
+static void
+test_range_functions ()
+{
+ sbitmap s = sbitmap_alloc (1024);
+ bitmap_clear (s);
+
+ ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
+ bitmap_set_bit (s, 100);
+
+ ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
+ ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
+ ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
+ ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
+ ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
+
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/11/2017 12:13 AM, Martin Liška wrote:
> Hi.
>
> This fixes some implementations mistakes in sbitmap.c
> (bitmap_bit_in_range_p). There's reference
> to implementation one can take inspiration from:
> https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/bitRange.html
>
> Problem with our implementation is that one can't do:
> (SBITMAP_ELT_TYPE)1 << SBITMAP_ELT_BITS (that would overflow)
> Thus I do conditionally ~(SBITMAP_ELT_TYPE)0 at some places in the code.
>
> I also added quite some unit tests for the method. But another questions pop
> up:
> 1) there are missing boundary asserts (or checking asserts) in sbitmap.c
> 2) we should probably include test-cases also for other functions
>
> I can work on that (probably later) if desired?
>
> And my patch breaks ssa-dse-26.c test-case, because now it properly returns
> true for:
>
> #0 bitmap_bit_in_range_p (bmap=0x21c4940, start=0, end=8) at
> ../../gcc/sbitmap.c:326
> #1 0x00d618f5 in live_bytes_read (use_ref=..., ref=0x7fffd480,
> live=0x21c4940) at ../../gcc/tree-ssa-dse.c:496
> #2 0x00d61c4d in dse_classify_store (ref=0x7fffd480,
> stmt=0x13ea7d70, use_stmt=0x7fffd470, byte_tracking_enabled=true,
> live_bytes=0x21c4940) at ../../gcc/tree-ssa-dse.c:594
> #3 0x00d6235b in dse_dom_walker::dse_optimize_stmt
> (this=0x7fffd5c0, gsi=0x7fffd530) at ../../gcc/tree-ssa-dse.c:820
> #4 0x00d62461 in dse_dom_walker::before_dom_children
> (this=0x7fffd5c0, bb=0x13d76270) at ../../gcc/tree-ssa-dse.c:852
> #5 0x013b1698 in dom_walker::walk (this=0x7fffd5c0,
> bb=0x13d76270) at ../../gcc/domwalk.c:308
> #6 0x00d625ac in (anonymous namespace)::pass_dse::execute
> (this=0x21d58c0, fun=0x13eac0b0) at ../../gcc/tree-ssa-dse.c:906
> #7 0x00b27441 in execute_one_pass (pass=pass@entry=0x21d58c0) at
> ../../gcc/passes.c:2495
> #8 0x00b27d01 in execute_pass_list_1 (pass=0x21d58c0) at
> ../../gcc/passes.c:2584
> #9 0x00b27d13 in execute_pass_list_1 (pass=0x21d5480) at
> ../../gcc/passes.c:2585
> #10 0x00b27d55 in execute_pass_list (fn=,
> pass=) at ../../gcc/passes.c:2595
> #11 0x00b26681 in do_per_function_toporder
> (callback=callback@entry=0xb27d40 ,
> data=0x21d5300) at ../../gcc/passes.c:1737
> #12 0x00b283d7 in execute_ipa_pass_list (pass=0x21d52a0) at
> ../../gcc/passes.c:2935
> #13 0x007d29d2 in ipa_passes () at ../../gcc/cgraphunit.c:2399
> #14 symbol_table::compile (this=this@entry=0x13d6e100) at
> ../../gcc/cgraphunit.c:2534
> #15 0x007d5277 in symbol_table::compile (this=0x13d6e100) at
> ../../gcc/cgraphunit.c:2695
> #16 symbol_table::finalize_compilation_unit (this=0x13d6e100) at
> ../../gcc/cgraphunit.c:2692
> #17 0x00c118ac in compile_file () at ../../gcc/toplev.c:481
> #18 0x00c13eee in do_compile () at ../../gcc/toplev.c:2037
> #19 0x00c141da in toplev::main (this=0x7fffd85e, argc=21,
> argv=0x7fffd958) at ../../gcc/toplev.c:2172
> #20 0x0061aeab in main (argc=21, argv=0x7fffd958) at
> ../../gcc/main.c:39
>
> (gdb) p debug(bmap)
> n_bits = 256, set = {8 9 10 11 12 13 14 15 }
>
> Jeff can you please help me?
> Apart from that the patch can bootstrap on ppc64le-redhat-linux and survives
> regression tests.
I think it's an off-by-1 error in the call to in_range_p. It's an
inclusive check so it's checking 0, 1, 2, 3, 4, 5, 6, 7, 8 -- which
covers 9 bytes. We really just wanted to cover 8 bytes. I want to look
at the rest of tree-ssa-dse.c so see if there are other instances before
checking in that fix.
bitmap_bit_in_range_p is almost a direct copy from bitmap_set_range.
You might want to peek bitmap_set_range and see if it has the same set
of bugs.
jeff
Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
On 10/11/2017 12:13 AM, Martin Liška wrote:
> Hi.
>
> This fixes some implementations mistakes in sbitmap.c
> (bitmap_bit_in_range_p). There's reference
> to implementation one can take inspiration from:
> https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/bitRange.html
>
> Problem with our implementation is that one can't do:
> (SBITMAP_ELT_TYPE)1 << SBITMAP_ELT_BITS (that would overflow)
> Thus I do conditionally ~(SBITMAP_ELT_TYPE)0 at some places in the code.
>
> I also added quite some unit tests for the method. But another questions pop
> up:
> 1) there are missing boundary asserts (or checking asserts) in sbitmap.c
> 2) we should probably include test-cases also for other functions
>
> I can work on that (probably later) if desired?
>
> And my patch breaks ssa-dse-26.c test-case, because now it properly returns
> true for:
>
> #0 bitmap_bit_in_range_p (bmap=0x21c4940, start=0, end=8) at
> ../../gcc/sbitmap.c:326
> #1 0x00d618f5 in live_bytes_read (use_ref=..., ref=0x7fffd480,
> live=0x21c4940) at ../../gcc/tree-ssa-dse.c:496
> #2 0x00d61c4d in dse_classify_store (ref=0x7fffd480,
> stmt=0x13ea7d70, use_stmt=0x7fffd470, byte_tracking_enabled=true,
> live_bytes=0x21c4940) at ../../gcc/tree-ssa-dse.c:594
> #3 0x00d6235b in dse_dom_walker::dse_optimize_stmt
> (this=0x7fffd5c0, gsi=0x7fffd530) at ../../gcc/tree-ssa-dse.c:820
> #4 0x00d62461 in dse_dom_walker::before_dom_children
> (this=0x7fffd5c0, bb=0x13d76270) at ../../gcc/tree-ssa-dse.c:852
> #5 0x013b1698 in dom_walker::walk (this=0x7fffd5c0,
> bb=0x13d76270) at ../../gcc/domwalk.c:308
> #6 0x00d625ac in (anonymous namespace)::pass_dse::execute
> (this=0x21d58c0, fun=0x13eac0b0) at ../../gcc/tree-ssa-dse.c:906
> #7 0x00b27441 in execute_one_pass (pass=pass@entry=0x21d58c0) at
> ../../gcc/passes.c:2495
> #8 0x00b27d01 in execute_pass_list_1 (pass=0x21d58c0) at
> ../../gcc/passes.c:2584
> #9 0x00b27d13 in execute_pass_list_1 (pass=0x21d5480) at
> ../../gcc/passes.c:2585
> #10 0x00b27d55 in execute_pass_list (fn=,
> pass=) at ../../gcc/passes.c:2595
> #11 0x00b26681 in do_per_function_toporder
> (callback=callback@entry=0xb27d40 ,
> data=0x21d5300) at ../../gcc/passes.c:1737
> #12 0x00b283d7 in execute_ipa_pass_list (pass=0x21d52a0) at
> ../../gcc/passes.c:2935
> #13 0x007d29d2 in ipa_passes () at ../../gcc/cgraphunit.c:2399
> #14 symbol_table::compile (this=this@entry=0x13d6e100) at
> ../../gcc/cgraphunit.c:2534
> #15 0x007d5277 in symbol_table::compile (this=0x13d6e100) at
> ../../gcc/cgraphunit.c:2695
> #16 symbol_table::finalize_compilation_unit (this=0x13d6e100) at
> ../../gcc/cgraphunit.c:2692
> #17 0x00c118ac in compile_file () at ../../gcc/toplev.c:481
> #18 0x00c13eee in do_compile () at ../../gcc/toplev.c:2037
> #19 0x00c141da in toplev::main (this=0x7fffd85e, argc=21,
> argv=0x7fffd958) at ../../gcc/toplev.c:2172
> #20 0x0061aeab in main (argc=21, argv=0x7fffd958) at
> ../../gcc/main.c:39
>
> (gdb) p debug(bmap)
> n_bits = 256, set = {8 9 10 11 12 13 14 15 }
>
> Jeff can you please help me?
> Apart from that the patch can bootstrap on ppc64le-redhat-linux and survives
> regression tests.
>
> Ready to be installed?
> Martin
>
> Thanks,
> Martin
>
> gcc/ChangeLog:
>
> 2017-10-10 Martin Liska
>
> PR tree-optimization/82493
> * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation.
> (test_range_functions): New function.
> (sbitmap_c_tests): Likewise.
> * selftest-run-tests.c (selftest::run_tests): Run new tests.
> * selftest.h (sbitmap_c_tests): New function.
Go ahead and install. I'll dig into the -26 testcase.
jeff
