restricted pointer tweak

[Tom MacDonald]

In the last NCEG mailing, Bill Homer's document 93-040 proposes an edit to
the restricted pointer proposal.  I wanted to introduce this issue before
the next meeting in Hawaii.  I also hope to keep this relatively short
because then you're more likely to read it :^)

Recently we discovered that the following example didn't behave as
expected (nor as advertised):

	void f(int n, int * restrict * restrict p,
               int * restrict * restrict q) {

	     int i, j;             /* Without edit, */
	     for(i=0; i<n; i++)    /* optimization  */
	       for(j=1; j<n; j++)  /* is inhibited. */
	         p[i][j] += q[i][j-1];

	}

This is contrary to the "just like an array" paradigm we've preached.

The problem is with the following 5 words in the formal definition:

	If O is modified, then

The idea was that it's OK for two restricted pointers to point to the same
object if you're only reading from the object (after all, no harm's done
if your just reading it).  However, with pointers to pointers, there are
two pointer objects and a final target object.  That's three different
objects all total.  These 5 words only talk about a single dereference;
thus they sometimes exclude the final target object altogether.  So, if
you don't modify the 2nd pointer object, unwanted aliasing was permitted.

We always wanted the example above to behave like:

        void g(int n, int p[][n], q[][n]) {

             int i, j;
             for(i=0; i<n; i++)
               for(j=1; j<n; j++)
                 p[i][j] += q[i][j-1];

        }

with the assumption that `p' and `q' don't point to the same object.

In general, the type modifier "* restrict" can always be replaced with
"[]" for alias analysis purposes.  The idea being that, an optimizer can
look at two lvalues, temporarily replace all "* restrict" modifiers with
"[]" modifiers, do the alias analysis, then apply the results of that
analysis to the original types of the lvalues.  If your optimizer can
handle arrays, it can now handle restricted pointers.

By deleting the words "If O is modified, then" from the formal definition,
we can once again operate under the assumption that "it's just like an
array for alias analysis purposes."

What's lost by this change is that it's no longer well defined to call the
following function:

	void h(
	   int n,
	   int * restrict * restrict p1,
	   int * restrict * restrict p2,
	   int * restrict * restrict p3)
	{
	   int i, j;

	   for (i=0, i<n, i++)
	      for (j=0, j<n, j++)
		 p1[i][j] = p2[i][j] + p3[i][j]; /* optimizations allowed */
	}

with the following invocation:

	h(a, b, b)  /* Error, 2nd & 3rd args are aliases */

The offending 5 words intended to allow such a call to `h' because it
seemed innocuous, but it turns out they do more harm than good.

Tom MacDonald