| Message ID | 9c9fd60f-cb7a-e702-aabb-9e31dca6a92a@suse.cz |
|---|---|
| State | New |
| Headers | show |
| Series | Fix bitmap_bit_in_range_p (PR tree-optimization/82493). | expand |
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 0x0000000000d618f5 in live_bytes_read (use_ref=..., ref=0x7fffffffd480, live=0x21c4940) at ../../gcc/tree-ssa-dse.c:496 > #2 0x0000000000d61c4d in dse_classify_store (ref=0x7fffffffd480, stmt=0x155553ea7d70, use_stmt=0x7fffffffd470, byte_tracking_enabled=true, live_bytes=0x21c4940) at ../../gcc/tree-ssa-dse.c:594 > #3 0x0000000000d6235b in dse_dom_walker::dse_optimize_stmt (this=0x7fffffffd5c0, gsi=0x7fffffffd530) at ../../gcc/tree-ssa-dse.c:820 > #4 0x0000000000d62461 in dse_dom_walker::before_dom_children (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/tree-ssa-dse.c:852 > #5 0x00000000013b1698 in dom_walker::walk (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/domwalk.c:308 > #6 0x0000000000d625ac in (anonymous namespace)::pass_dse::execute (this=0x21d58c0, fun=0x155553eac0b0) at ../../gcc/tree-ssa-dse.c:906 > #7 0x0000000000b27441 in execute_one_pass (pass=pass@entry=0x21d58c0) at ../../gcc/passes.c:2495 > #8 0x0000000000b27d01 in execute_pass_list_1 (pass=0x21d58c0) at ../../gcc/passes.c:2584 > #9 0x0000000000b27d13 in execute_pass_list_1 (pass=0x21d5480) at ../../gcc/passes.c:2585 > #10 0x0000000000b27d55 in execute_pass_list (fn=<optimized out>, pass=<optimized out>) at ../../gcc/passes.c:2595 > #11 0x0000000000b26681 in do_per_function_toporder (callback=callback@entry=0xb27d40 <execute_pass_list(function*, opt_pass*)>, data=0x21d5300) at ../../gcc/passes.c:1737 > #12 0x0000000000b283d7 in execute_ipa_pass_list (pass=0x21d52a0) at ../../gcc/passes.c:2935 > #13 0x00000000007d29d2 in ipa_passes () at ../../gcc/cgraphunit.c:2399 > #14 symbol_table::compile (this=this@entry=0x155553d6e100) at ../../gcc/cgraphunit.c:2534 > #15 0x00000000007d5277 in symbol_table::compile (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2695 > #16 symbol_table::finalize_compilation_unit (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2692 > #17 0x0000000000c118ac in compile_file () at ../../gcc/toplev.c:481 > #18 0x0000000000c13eee in do_compile () at ../../gcc/toplev.c:2037 > #19 0x0000000000c141da in toplev::main (this=0x7fffffffd85e, argc=21, argv=0x7fffffffd958) at ../../gcc/toplev.c:2172 > #20 0x000000000061aeab in main (argc=21, argv=0x7fffffffd958) 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 <mliska@suse.cz> > > 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
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 0x0000000000d618f5 in live_bytes_read (use_ref=..., ref=0x7fffffffd480, live=0x21c4940) at ../../gcc/tree-ssa-dse.c:496 > #2 0x0000000000d61c4d in dse_classify_store (ref=0x7fffffffd480, stmt=0x155553ea7d70, use_stmt=0x7fffffffd470, byte_tracking_enabled=true, live_bytes=0x21c4940) at ../../gcc/tree-ssa-dse.c:594 > #3 0x0000000000d6235b in dse_dom_walker::dse_optimize_stmt (this=0x7fffffffd5c0, gsi=0x7fffffffd530) at ../../gcc/tree-ssa-dse.c:820 > #4 0x0000000000d62461 in dse_dom_walker::before_dom_children (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/tree-ssa-dse.c:852 > #5 0x00000000013b1698 in dom_walker::walk (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/domwalk.c:308 > #6 0x0000000000d625ac in (anonymous namespace)::pass_dse::execute (this=0x21d58c0, fun=0x155553eac0b0) at ../../gcc/tree-ssa-dse.c:906 > #7 0x0000000000b27441 in execute_one_pass (pass=pass@entry=0x21d58c0) at ../../gcc/passes.c:2495 > #8 0x0000000000b27d01 in execute_pass_list_1 (pass=0x21d58c0) at ../../gcc/passes.c:2584 > #9 0x0000000000b27d13 in execute_pass_list_1 (pass=0x21d5480) at ../../gcc/passes.c:2585 > #10 0x0000000000b27d55 in execute_pass_list (fn=<optimized out>, pass=<optimized out>) at ../../gcc/passes.c:2595 > #11 0x0000000000b26681 in do_per_function_toporder (callback=callback@entry=0xb27d40 <execute_pass_list(function*, opt_pass*)>, data=0x21d5300) at ../../gcc/passes.c:1737 > #12 0x0000000000b283d7 in execute_ipa_pass_list (pass=0x21d52a0) at ../../gcc/passes.c:2935 > #13 0x00000000007d29d2 in ipa_passes () at ../../gcc/cgraphunit.c:2399 > #14 symbol_table::compile (this=this@entry=0x155553d6e100) at ../../gcc/cgraphunit.c:2534 > #15 0x00000000007d5277 in symbol_table::compile (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2695 > #16 symbol_table::finalize_compilation_unit (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2692 > #17 0x0000000000c118ac in compile_file () at ../../gcc/toplev.c:481 > #18 0x0000000000c13eee in do_compile () at ../../gcc/toplev.c:2037 > #19 0x0000000000c141da in toplev::main (this=0x7fffffffd85e, argc=21, argv=0x7fffffffd958) at ../../gcc/toplev.c:2172 > #20 0x000000000061aeab in main (argc=21, argv=0x7fffffffd958) 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
On 10/11/2017 12:13 AM, Martin Liška wrote: > 2017-10-10 Martin Liska <mliska@suse.cz> > > 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 <law@138bc75d-0d04-0410-961f-82ee72b054a4> Date: Thu Oct 12 21:53:21 2017 +0000 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 <mliska@suse.cz> + + 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 <meissner@linux.vnet.ibm.com> * 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)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100)); + ASSERT_TRUE (bitmap_bit_p (s, 100)); + + s = sbitmap_alloc (64); + bitmap_clear (s); + bitmap_set_bit (s, 63); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63)); + ASSERT_TRUE (bitmap_bit_p (s, 63)); + + s = sbitmap_alloc (1024); + bitmap_clear (s); + bitmap_set_bit (s, 128); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023)); + + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254)); + ASSERT_TRUE (bitmap_bit_p (s, 128)); + + bitmap_clear (s); + bitmap_set_bit (s, 8); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8)); + ASSERT_TRUE (bitmap_bit_p (s, 8)); + + bitmap_clear (s); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256)); + + bitmap_set_bit (s, 0); + bitmap_set_bit (s, 16); + bitmap_set_bit (s, 32); + bitmap_set_bit (s, 48); + bitmap_set_bit (s, 64); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023)); +} + +/* Run all of the selftests within this file. */ + +void +sbitmap_c_tests () +{ + test_range_functions (); +} + +} // namespace selftest +#endif /* CHECKING_P */ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index 30e476d14c5..5c84f3a0737 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -56,6 +56,7 @@ selftest::run_tests () /* Low-level data structures. */ bitmap_c_tests (); + sbitmap_c_tests (); et_forest_c_tests (); hash_map_tests_c_tests (); hash_set_tests_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index 0572fefd281..2e649a70b9e 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -171,6 +171,7 @@ extern const char *path_to_selftest_files; /* Declarations for specific families of tests (by source file), in alphabetical order. */ extern void bitmap_c_tests (); +extern void sbitmap_c_tests (); extern void diagnostic_c_tests (); extern void diagnostic_show_locus_c_tests (); extern void edit_context_c_tests (); diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 87e2fce9ac5..9d6cb146436 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -493,7 +493,7 @@ live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) /* Now check if any of the remaining bits in use_ref are set in LIVE. */ unsigned int start = (use_ref.offset - ref->offset) / BITS_PER_UNIT; - unsigned int end = (use_ref.offset + use_ref.size) / BITS_PER_UNIT; + unsigned int end = ((use_ref.offset + use_ref.size) / BITS_PER_UNIT) - 1; return bitmap_bit_in_range_p (live, start, end); } return true;
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 <mliska@suse.cz> >> >> 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
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 <mliska@suse.cz> >> >> 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 <mliska@suse.cz> 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,9 @@ bitmap_intersect_p (const_sbitmap a, const_sbitmap b) bool bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) { + bitmap_check_sizes (a, b); + bitmap_check_sizes (b, dst); + unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; @@ -577,6 +600,9 @@ bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) bool bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) { + bitmap_check_sizes (a, b); + bitmap_check_sizes (b, dst); + unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; @@ -599,6 +625,9 @@ bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) bool bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) { + bitmap_check_sizes (a, b); + bitmap_check_sizes (b, dst); + unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; @@ -620,6 +649,8 @@ bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) bool bitmap_subset_p (const_sbitmap a, const_sbitmap b) { + bitmap_check_sizes (a, b); + unsigned int i, n = a->size; const_sbitmap_ptr ap, bp; @@ -636,6 +667,10 @@ bitmap_subset_p (const_sbitmap a, const_sbitmap b) bool bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) { + bitmap_check_sizes (a, b); + bitmap_check_sizes (b, c); + bitmap_check_sizes (c, dst); + unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; @@ -659,6 +694,10 @@ bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) bool bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) { + bitmap_check_sizes (a, b); + bitmap_check_sizes (b, c); + bitmap_check_sizes (c, dst); + unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index ff52e939bf3..a5ff0685e43 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -96,10 +96,29 @@ struct simple_bitmap_def /* Return the number of bits in BITMAP. */ #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) +/* Verify that access at INDEX in bitmap MAP is valid. */ + +static inline void +bitmap_check_index (const_sbitmap map, int index) +{ + gcc_checking_assert (index >= 0); + gcc_checking_assert ((unsigned int)index < map->n_bits); +} + +/* Verify that bitmaps A and B have same size. */ + +static inline void +bitmap_check_sizes (const_sbitmap a, const_sbitmap b) +{ + gcc_checking_assert (a->n_bits == b->n_bits); +} + /* Test if bit number bitno in the bitmap is set. */ static inline SBITMAP_ELT_TYPE bitmap_bit_p (const_sbitmap map, int bitno) { + bitmap_check_index (map, bitno); + size_t i = bitno / SBITMAP_ELT_BITS; unsigned int s = bitno % SBITMAP_ELT_BITS; return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1; @@ -110,6 +129,8 @@ bitmap_bit_p (const_sbitmap map, int bitno) static inline void bitmap_set_bit (sbitmap map, int bitno) { + bitmap_check_index (map, bitno); + map->elms[bitno / SBITMAP_ELT_BITS] |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; } @@ -119,6 +140,8 @@ bitmap_set_bit (sbitmap map, int bitno) static inline void bitmap_clear_bit (sbitmap map, int bitno) { + bitmap_check_index (map, bitno); + map->elms[bitno / SBITMAP_ELT_BITS] &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); } @@ -148,6 +171,8 @@ static inline void bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED) { + bitmap_check_index (bmp, min); + i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; i->bit_num = min; i->size = bmp->size;
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 <mliska@suse.cz> >>> >>> 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 <mliska@suse.cz> 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 <mliska@suse.cz> * 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
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 <mliska@suse.cz> >>>> >>>> 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
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 <mliska@suse.cz> >>> >>> 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
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 <mliska@suse.cz> >>>> >>>> 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? Thanks, Martin
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 <mliska@suse.cz> >>>>> >>>>> 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
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 <mliska@suse.cz> >>> >>> 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 <mliska@suse.cz> > 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
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)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100)); + ASSERT_TRUE (bitmap_bit_p (s, 100)); + + s = sbitmap_alloc (64); + bitmap_clear (s); + bitmap_set_bit (s, 63); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63)); + ASSERT_TRUE (bitmap_bit_p (s, 63)); + + s = sbitmap_alloc (1024); + bitmap_clear (s); + bitmap_set_bit (s, 128); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023)); + + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254)); + ASSERT_TRUE (bitmap_bit_p (s, 128)); + + bitmap_clear (s); + bitmap_set_bit (s, 8); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8)); + ASSERT_TRUE (bitmap_bit_p (s, 8)); + + bitmap_clear (s); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256)); + + bitmap_set_bit (s, 0); + bitmap_set_bit (s, 16); + bitmap_set_bit (s, 32); + bitmap_set_bit (s, 48); + bitmap_set_bit (s, 64); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023)); +} + +/* Run all of the selftests within this file. */ + +void +sbitmap_c_tests () +{ + test_range_functions (); +} + +} // namespace selftest +#endif /* CHECKING_P */ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index 30e476d14c5..5c84f3a0737 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -56,6 +56,7 @@ selftest::run_tests () /* Low-level data structures. */ bitmap_c_tests (); + sbitmap_c_tests (); et_forest_c_tests (); hash_map_tests_c_tests (); hash_set_tests_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index 0572fefd281..2e649a70b9e 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -171,6 +171,7 @@ extern const char *path_to_selftest_files; /* Declarations for specific families of tests (by source file), in alphabetical order. */ extern void bitmap_c_tests (); +extern void sbitmap_c_tests (); extern void diagnostic_c_tests (); extern void diagnostic_show_locus_c_tests (); extern void edit_context_c_tests ();
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 0x0000000000d618f5 in live_bytes_read (use_ref=..., ref=0x7fffffffd480, live=0x21c4940) at ../../gcc/tree-ssa-dse.c:496 #2 0x0000000000d61c4d in dse_classify_store (ref=0x7fffffffd480, stmt=0x155553ea7d70, use_stmt=0x7fffffffd470, byte_tracking_enabled=true, live_bytes=0x21c4940) at ../../gcc/tree-ssa-dse.c:594 #3 0x0000000000d6235b in dse_dom_walker::dse_optimize_stmt (this=0x7fffffffd5c0, gsi=0x7fffffffd530) at ../../gcc/tree-ssa-dse.c:820 #4 0x0000000000d62461 in dse_dom_walker::before_dom_children (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/tree-ssa-dse.c:852 #5 0x00000000013b1698 in dom_walker::walk (this=0x7fffffffd5c0, bb=0x155553d76270) at ../../gcc/domwalk.c:308 #6 0x0000000000d625ac in (anonymous namespace)::pass_dse::execute (this=0x21d58c0, fun=0x155553eac0b0) at ../../gcc/tree-ssa-dse.c:906 #7 0x0000000000b27441 in execute_one_pass (pass=pass@entry=0x21d58c0) at ../../gcc/passes.c:2495 #8 0x0000000000b27d01 in execute_pass_list_1 (pass=0x21d58c0) at ../../gcc/passes.c:2584 #9 0x0000000000b27d13 in execute_pass_list_1 (pass=0x21d5480) at ../../gcc/passes.c:2585 #10 0x0000000000b27d55 in execute_pass_list (fn=<optimized out>, pass=<optimized out>) at ../../gcc/passes.c:2595 #11 0x0000000000b26681 in do_per_function_toporder (callback=callback@entry=0xb27d40 <execute_pass_list(function*, opt_pass*)>, data=0x21d5300) at ../../gcc/passes.c:1737 #12 0x0000000000b283d7 in execute_ipa_pass_list (pass=0x21d52a0) at ../../gcc/passes.c:2935 #13 0x00000000007d29d2 in ipa_passes () at ../../gcc/cgraphunit.c:2399 #14 symbol_table::compile (this=this@entry=0x155553d6e100) at ../../gcc/cgraphunit.c:2534 #15 0x00000000007d5277 in symbol_table::compile (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2695 #16 symbol_table::finalize_compilation_unit (this=0x155553d6e100) at ../../gcc/cgraphunit.c:2692 #17 0x0000000000c118ac in compile_file () at ../../gcc/toplev.c:481 #18 0x0000000000c13eee in do_compile () at ../../gcc/toplev.c:2037 #19 0x0000000000c141da in toplev::main (this=0x7fffffffd85e, argc=21, argv=0x7fffffffd958) at ../../gcc/toplev.c:2172 #20 0x000000000061aeab in main (argc=21, argv=0x7fffffffd958) 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 <mliska@suse.cz> 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. --- gcc/sbitmap.c | 118 ++++++++++++++++++++++++++++++++++++++++------- gcc/selftest-run-tests.c | 1 + gcc/selftest.h | 1 + 3 files changed, 103 insertions(+), 17 deletions(-)