Re: PATCH to implement `restrict' in C

[Mark Mitchell <mark at markmitchell dot com>]

    On Fri, Oct 09, 1998 at 01:15:28PM -0700, Mark Mitchell wrote:
    >   int* restrict i;
    >   int* restrict j;
    >   int* k;
    > 
    > we know that `i' and `j' cannot point to the same thing, but either
    > might alias the storage point to by `k'.

    This was not my understanding of the definition of restrict.

Unfortunately, your understanding is incorrect. :-)

    My understanding is that it is intended to signify that that
    pointer contains the _only_ reference to a block of memory.

Nope.  This, however, is a common misperception.

    Quoting n2620.pdf (whatever version of the c9x draft that was):
    ~~~~~
    4  During each execution of [block] B, let A be the array object that is
       determined dynamically by all references through pointer expressions
       based on [the restricted pointer] P. Then _all_ [emph theirs] references
       to values of A shall be through pointer expressions based on P.
    ...
    7     1.  The file scope declarations
	    int * restrict a;
	    int * restrict b;
	    extern int c[];
	  assert that if an object is referenced using the value of one of a,
	  b, or c, then it is never referenced using the value of either of
	  the other two.
    ~~~~~

That's because, in this case, `c' is an actual object.  Therefore, `c'
cannot be "based on" `a' because no amount of assigning to `a' will
change the value of `c'.  In particular:

  "A pointer expression E is said to be based on P if ... modifying P to
   point to a copy of the array into which it formerly pointed would
   change the value of E."

Here, P is a restricted pointer (in our case `a') and E is an
expression (in our case `c').  Clearly, `c' cannot become based on
`a'.  Therefore, since "all references to A shall be through pointer
expressions based on `P" it is illegal to ever use `a' reference
memory in `c'.  This is similar to the example given in the draft:

  void h(int n, int* const restrict p, int* const q, int* const r)
  { ... }

where, as explained in the draft, the const-ness of `q' and `r'
prevents them from becoming based on `p'.  However, if they were
non-const, all bets are off; it would be legal to write:

  q = p;
  q[0] = p[0];

say.  Similarly, the following code is conforming:

  int* f(int* p) { return p; }
  void g(int* restrict p)
  {
    p[0] = f(p)[0];
  }

where here, of course, `f(p)' and `p' are the same pointer.  In
particular, `f(p)' is based on `p'; changing `p' to point somewhere
else would change the value of `f(p)'.

-- 
Mark Mitchell 			mark@markmitchell.com
Mark Mitchell Consulting	http://www.markmitchell.com