From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 48904 invoked by alias); 12 Oct 2017 02:21:23 -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 47811 invoked by uid 89); 12 Oct 2017 02:21:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.9 required=5.0 tests=BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=no version=3.3.2 spammy= X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 12 Oct 2017 02:21:21 +0000 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2D3725D68D; Thu, 12 Oct 2017 02:21:20 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 2D3725D68D Authentication-Results: ext-mx10.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx10.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=law@redhat.com Received: from localhost.localdomain (ovpn-112-4.rdu2.redhat.com [10.10.112.4]) by smtp.corp.redhat.com (Postfix) with ESMTP id 461E878209; Thu, 12 Oct 2017 02:21:18 +0000 (UTC) Subject: Re: [PATCH] Fix bitmap_bit_in_range_p (PR tree-optimization/82493). To: =?UTF-8?Q?Martin_Li=c5=a1ka?= , gcc-patches@gcc.gnu.org References: <9c9fd60f-cb7a-e702-aabb-9e31dca6a92a@suse.cz> From: Jeff Law Message-ID: <0f8eea75-2e1a-536c-a905-5177b59fd4fe@redhat.com> Date: Thu, 12 Oct 2017 04:48:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 In-Reply-To: <9c9fd60f-cb7a-e702-aabb-9e31dca6a92a@suse.cz> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2017-10/txt/msg00719.txt.bz2 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=, 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. 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