[PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Martin Liška]

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

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(-)



[-- Attachment #2: 0001-Fix-bitmap_bit_in_range_p-PR-tree-optimization-82493.patch --]
[-- Type: text/x-patch, Size: 6187 bytes --]

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 ();

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

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

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 8066 bytes --]

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;

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Martin Liška]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Martin Liška]

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

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

[-- Attachment #2: 0002-Add-gcc_checking_assert-for-sbitmap.c.patch --]
[-- Type: text/x-patch, Size: 6835 bytes --]

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;
-- 
2.14.2

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Martin Liška]

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

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

[-- Attachment #2: 0001-Add-selftests-for-bitmap_set_range.patch --]
[-- Type: text/x-patch, Size: 2915 bytes --]

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
-- 
2.14.2

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Martin Liška]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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

Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

[Jeff Law]

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