From patchwork Thu Jun 16 06:39:34 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 100595 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 972BFB6F9D for ; Thu, 16 Jun 2011 16:38:50 +1000 (EST) Received: (qmail 15549 invoked by alias); 16 Jun 2011 06:38:48 -0000 Received: (qmail 15512 invoked by uid 22791); 16 Jun 2011 06:38:47 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SPF_FAIL X-Spam-Check-By: sourceware.org Received: from smtp-vbr4.xs4all.nl (HELO smtp-vbr4.xs4all.nl) (194.109.24.24) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 16 Jun 2011 06:38:32 +0000 Received: from [192.168.1.68] (teejay.xs4all.nl [213.84.119.160]) (authenticated bits=0) by smtp-vbr4.xs4all.nl (8.13.8/8.13.8) with ESMTP id p5G6cTWh004058 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 16 Jun 2011 08:38:30 +0200 (CEST) (envelope-from vries@codesourcery.com) Message-ID: <4DF9A526.9060906@codesourcery.com> Date: Thu, 16 Jun 2011 08:39:34 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Lightning/1.0b2 Thunderbird/3.1.10 MIME-Version: 1.0 To: Zdenek Dvorak CC: gcc-patches@gcc.gnu.org Subject: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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. OK for trunk? Thanks, - Tom 2011-06-15 Tom de Vries PR target/45098 * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Disallow NULL pointer for pointer arithmetic. diff -u gcc/tree-ssa-loop-niter.c (working copy) gcc/tree-ssa-loop-niter.c (working copy) --- gcc/tree-ssa-loop-niter.c (working copy) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -2875,6 +2875,16 @@ low = lower_bound_in_type (type, type); high = upper_bound_in_type (type, type); + /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot + produce a NULL pointer. The contrary would mean NULL points to an object, + while NULL is supposed to compare unequal with the address of all objects. + Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a + NULL pointer since that would mean wrapping, which we assume here not to + happen. So, we can exclude NULL from the valid range of pointer + arithmetic. */ + if (ptrdiff_type_node != NULL_TREE && int_cst_value (low) == 0) + low = fold_build2 (PLUS_EXPR, TREE_TYPE (low), low, step); + record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); }