From: Zdenek Dvorak <rakdver@kam.mff.cuni.cz>
To: Tom de Vries <vries@codesourcery.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH PR45098] Disallow NULL pointer in pointer arithmetic
Date: Thu, 16 Jun 2011 07:34:00 -0000 [thread overview]
Message-ID: <20110616072405.GA6045@kam.mff.cuni.cz> (raw)
In-Reply-To: <4DF9A526.9060906@codesourcery.com>
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.
this reasoning seems slightly inaccurate to me: the loop is typically translated
as
if (n > 0)
{
i = 0;
start:
sum += foo (&array[i]);
i++;
if (i < n)
goto start;
}
This means that if the array access is performed <= x times, then the exit condition
of the loop is tested <= x times (not counting the copied header). This could be
exploited to fix the problem as well.
> 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.
Sounds reasonable to me.
> 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).
At least in principle, the variable could have initial value 0x1, so this is a bit
incorrect. (alignment of the memory reference, 0xffffffff, 0x4) should work, though.
> 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.
The middle-end operations in general follow the C semantics, unless explicitly
specified otherwise (e.g. language-specific alias analysis rules, ...). So, I think
you can drop this test.
Zdenek
next prev parent reply other threads:[~2011-06-16 7:24 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-06-16 6:42 Tom de Vries
2011-06-16 6:51 ` Tom de Vries
2011-06-16 7:34 ` Zdenek Dvorak [this message]
2011-06-16 12:22 ` Tom de Vries
2011-06-16 15:33 ` Zdenek Dvorak
2011-06-16 15:42 ` Richard Guenther
2011-06-16 15:54 ` Zdenek Dvorak
2011-06-16 18:10 ` Tom de Vries
2011-06-16 22:03 ` Jeff Law
2011-06-17 10:44 ` Tom de Vries
2011-06-17 10:56 ` Richard Guenther
2011-06-17 10:57 ` Zdenek Dvorak
2011-06-17 11:13 ` Richard Guenther
2011-06-17 11:22 ` Zdenek Dvorak
2011-06-17 13:01 ` Richard Guenther
2011-06-17 14:57 ` Zdenek Dvorak
2011-06-17 18:24 ` Jeff Law
2011-06-20 11:06 ` Richard Guenther
2011-06-20 12:26 ` Zdenek Dvorak
2011-06-20 12:41 ` Zdenek Dvorak
2011-06-20 13:29 ` Richard Guenther
2011-06-20 13:35 ` Michael Matz
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20110616072405.GA6045@kam.mff.cuni.cz \
--to=rakdver@kam.mff.cuni.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=vries@codesourcery.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).