From 0af377c15a40ae329f6019155d07857df452f42b Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Thu, 12 Oct 2017 23:53:21 +0200 Subject: [PATCH] re PR tree-optimization/82493 (UBSAN in gcc/sbitmap.c:368:28: runtime error: shift exponent 64 is too large for 64-bit type 'long unsigned int') 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. From-SVN: r253699 --- gcc/ChangeLog | 11 ++++ gcc/sbitmap.c | 118 +++++++++++++++++++++++++++++++++------ gcc/selftest-run-tests.c | 1 + gcc/selftest.h | 1 + gcc/tree-ssa-dse.c | 2 +- 5 files changed, 115 insertions(+), 18 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 20fb303d03a..b5981edddc4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2017-10-12 Martin Liska + + PR tree-optimization/82493 + * sbitmap.c (bitmap_bit_in_range_p): Fix the implementation. + (test_range_functions): New function. + (sbitmap_c_tests): Likewise. + * selftest-run-tests.c (selftest::run_tests): Run new tests. + * selftest.h (sbitmap_c_tests): New function. + + * tree-ssa-dse.c (live_bytes_read): Fix thinko. + 2017-10-12 Michael Meissner * config/rs6000/amo.h: Fix spacing issue. diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 4bf13a11a1d..baef4d05f0d 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "sbitmap.h" +#include "selftest.h" typedef SBITMAP_ELT_TYPE *sbitmap_ptr; typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; @@ -322,29 +323,22 @@ bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count) bool bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end) { + gcc_checking_assert (start <= end); unsigned int start_word = start / SBITMAP_ELT_BITS; unsigned int start_bitno = start % SBITMAP_ELT_BITS; - /* Testing within a word, starting at the beginning of a word. */ - if (start_bitno == 0 && (end - start) < SBITMAP_ELT_BITS) - { - SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << (end - start)) - 1; - return (bmap->elms[start_word] & mask) != 0; - } - unsigned int end_word = end / SBITMAP_ELT_BITS; unsigned int end_bitno = end % SBITMAP_ELT_BITS; - /* Testing starts somewhere in the middle of a word. Test up to the - end of the word or the end of the requested region, whichever comes - first. */ + /* Check beginning of first word if different from zero. */ if (start_bitno != 0) { - unsigned int nbits = ((start_word == end_word) - ? end_bitno - start_bitno - : SBITMAP_ELT_BITS - start_bitno); - SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1; - mask <<= start_bitno; + SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0; + if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS) + high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1; + + SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1; + SBITMAP_ELT_TYPE mask = high_mask - low_mask; if (bmap->elms[start_word] & mask) return true; start_word++; @@ -364,8 +358,9 @@ bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end) } /* Now handle residuals in the last word. */ - SBITMAP_ELT_TYPE mask - = ((SBITMAP_ELT_TYPE)1 << (SBITMAP_ELT_BITS - end_bitno)) - 1; + SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0; + if (end_bitno + 1 < SBITMAP_ELT_BITS) + mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1; return (bmap->elms[start_word] & mask) != 0; } @@ -821,3 +816,92 @@ dump_bitmap_vector (FILE *file, const char *title, const char *subtitle, fprintf (file, "\n"); } + +#if CHECKING_P + +namespace selftest { + +/* Selftests for sbitmaps. */ + + +/* Verify range functions for sbitmap. */ + +static void +test_range_functions () +{ + sbitmap s = sbitmap_alloc (1024); + bitmap_clear (s); + + ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023)); + bitmap_set_bit (s, 100); + + ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99)); + ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100)); + ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100)); + 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; -- 2.30.2