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
