[PATCH PR45098] Disallow NULL pointer in pointer arithmetic

[Tom de Vries <vries at codesourcery dot 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.

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  <tom@codesourcery.com>

	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);
 }