From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7546 invoked by alias); 16 Jun 2011 22:01:29 -0000 Received: (qmail 7537 invoked by uid 22791); 16 Jun 2011 22:01:27 -0000 X-SWARE-Spam-Status: No, hits=-6.9 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_HI,SPF_HELO_PASS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 16 Jun 2011 22:01:14 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p5GM1396024319 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 16 Jun 2011 18:01:03 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p5GM129K006745; Thu, 16 Jun 2011 18:01:02 -0400 Received: from [10.3.113.98] (ovpn-113-98.phx2.redhat.com [10.3.113.98]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id p5GM10cn010773; Thu, 16 Jun 2011 18:01:01 -0400 Message-ID: <4DFA7D1C.9040105@redhat.com> Date: Thu, 16 Jun 2011 22:03:00 -0000 From: Jeff Law User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110428 Fedora/3.1.10-1.fc15 Lightning/1.0b3pre Thunderbird/3.1.10 MIME-Version: 1.0 To: Tom de Vries CC: Zdenek Dvorak , gcc-patches@gcc.gnu.org Subject: Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic References: <4DF9A526.9060906@codesourcery.com> In-Reply-To: <4DF9A526.9060906@codesourcery.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes 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 X-SW-Source: 2011-06/txt/msg01305.txt.bz2 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 06/16/11 00:39, Tom de Vries wrote: > Hi, > > Consider the following example. > > extern unsigned int foo (int*) __attribute__((pure)); > unsigned int > tr (int array[], int n) > { > unsigned int i; > unsigned int sum = 0; > for (i = 0; i < n; i++) > sum += foo (&array[i]); > return sum; > } > > For 32-bit pointers, the analysis in infer_loop_bounds_from_pointer_arith > currently concludes that the range of valid &array[i] is &array[0x0] to > &array[0x3fffffff], meaning 0x40000000 distinct values. > This implies that i < n is executed at most 0x40000001 times, and i < n > cannot be eliminated by an 32-bit iterator with step 4, since that one has > only 0x40000000 distinct values. > > The patch reasons that NULL cannot be used or produced by pointer > arithmetic, and that we can exclude the possibility of the NULL pointer in the > range. So the range of valid &array[i] is &array[0] to &array[0x3ffffffe], > meaning 0x3fffffff distinct values. > This implies that i < n is executed at most 0x40000000 times and i < n can be > eliminated. > > The patch implements this new limitation by changing the (low, high, step) > triplet in infer_loop_bounds_from_pointer_arith from (0x0, 0xffffffff, 0x4) > to (0x4, 0xffffffff, 0x4). > > I'm not too happy about the test for C-like language: ptrdiff_type_node != > NULL_TREE, but I'm not sure how else to test for this. > > Bootstrapped and reg-tested on x86_64. > > I will sent the adapted test cases in a separate email. Interesting. I'd never thought about the generation/use angle to prove a pointer was non-null. ISTM we could use that same logic to infer that more pointers are non-null in extract_range_from_binary_expr. Interested in tackling that improvement, obviously as an independent patch? jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJN+n0cAAoJEBRtltQi2kC7aRYH/1jyc0xmWEnzkxaMxdn9t5+p asGN79nl8BSPifZapn2R7brEt9uQQNT6oAe/4wlCr0qf5f0FwMUV8U2QH8uMuez3 gqO+PuqcF6dSxR5+qskgljSjjLndxdFuaiN1Lb95jR9Wg3l/Nv6NGpjdgAaWHiVk cmiuwAkVGSB46TGMMVnumFWTbXbXAK7udSk1PBDUZlY8Da+B9M2eGX9MuaPBNWvd YSHRpkVVFAlyJIpwdtAojE6T2korZQyHAmYqiuArBPYxAN7cLuV8Gl4AagzyHcVz Epkg7e0ayS1PnnQuH1JpAKGKH1DSlOmqo69JJpuL/kyaBh5lo4wu32RWHm/aGkY= =fESM -----END PGP SIGNATURE-----