From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 44319 invoked by alias); 11 Oct 2017 06:13:22 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 43343 invoked by uid 89); 11 Oct 2017 06:13:21 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 11 Oct 2017 06:13:19 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 29BB8ACFF; Wed, 11 Oct 2017 06:13:16 +0000 (UTC) From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Subject: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493). To: gcc-patches@gcc.gnu.org Cc: Jeff Law Message-ID: <9c9fd60f-cb7a-e702-aabb-9e31dca6a92a@suse.cz> Date: Wed, 11 Oct 2017 06:15:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------DA93C6649AB17AAA5D2CC397" X-IsSubscribed: yes X-SW-Source: 2017-10/txt/msg00635.txt.bz2 This is a multi-part message in MIME format. --------------DA93C6649AB17AAA5D2CC397 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Content-length: 3816 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=, pass=) at ../../gcc/passes.c:2595 #11 0x0000000000b26681 in do_per_function_toporder (callback=callback@entry=0xb27d40 , 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 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(-) --------------DA93C6649AB17AAA5D2CC397 Content-Type: text/x-patch; name="0001-Fix-bitmap_bit_in_range_p-PR-tree-optimization-82493.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-Fix-bitmap_bit_in_range_p-PR-tree-optimization-82493.pa"; filename*1="tch" Content-length: 6187 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 (); --------------DA93C6649AB17AAA5D2CC397--