Fix bitmap_bit_in_range_p (PR tree-optimization/82493).

Message ID 9c9fd60f-cb7a-e702-aabb-9e31dca6a92a@suse.cz
State New
Headers show
Series
  • Fix bitmap_bit_in_range_p (PR tree-optimization/82493).
Related show

Commit Message

Martin Liška Oct. 11, 2017, 6:13 a.m.
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(-)

Comments

Jeff Law Oct. 11, 2017, 5:37 p.m. | #1
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
Jeff Law Oct. 12, 2017, 2:21 a.m. | #2
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
Jeff Law Oct. 12, 2017, 9:54 p.m. | #3
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;
Martin Liška Oct. 13, 2017, 8:01 a.m. | #4
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
Martin Liška Oct. 13, 2017, 1:02 p.m. | #5
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;
Martin Liška Oct. 13, 2017, 1:03 p.m. | #6
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
Jeff Law Oct. 13, 2017, 2:14 p.m. | #7
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
Jeff Law Oct. 13, 2017, 2:59 p.m. | #8
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
Martin Liška Oct. 16, 2017, 12:03 p.m. | #9
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
Jeff Law Oct. 16, 2017, 2:47 p.m. | #10
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
Jeff Law Oct. 17, 2017, 5:30 p.m. | #11
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

Patch

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