% To format:
%     latex aug95.tex
%
% To preview the .dvi file created by latex, use either of:
%     xdvi aug95
%
% To print the .dvi file:
%     dvips aug95
%
\documentstyle[twoside]{article}
\title{
		Restricted Pointers\\
		     WG14/N448\\
		    X3J11/95-049
}
\author{
                          Bill Homer\\
                        Cray Research, Inc.\\
                        655F Lone Oak Drive\\
                        Eagan, MN  55121
} % end author
\date{August 23, 1995}

\topmargin -0.5in
\textheight 9.0in
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.3in

\begin{document}

\pagestyle{myheadings}
\markboth{\hfill WG14/N448, X3J11/95-049 \hfill Restricted Pointers}
	 {Restricted Pointers \hfill WG14/N448, X3J11/95-049 \hfill}

\maketitle
%%%begin-html-only
%%%\newtheorem{Caption}{}
%%%\newenvironment{Code}[2]{\begin{quotation}\begin{Caption}\label{#1}\end{Caption}{\em Figure~\ref{#1}. #2}}{\end{quotation}}
%%%end-html-only
%%%begin-latex-only
\newenvironment{Code}[2]{\begin{figure}[htbp]\small\caption{\label{#1}#2.}\begin{quote}}{\end{quote}\end{figure}}
%%%end-latex-only
\newcommand{\Example}[1]{Figure~\ref{#1}}

\section{Introduction}

This chapter describes a proposal for an additional type qualifier,
spelled \verb/restrict/.
Like the \verb/volatile/ type qualifier, \verb/restrict/ is
intended to affect compiler optimizations (though in the opposite
direction, by enabling rather inhibiting them).
Like the \verb/const/ type qualifier, \verb/restrict/ has semantic
rules to which a program must conform to avoid undefined behavior.
The proposed changes to the text of the C Standard, which are relatively 
small and confined to two sections, are presented after the rationale.

\section{Rationale}

\subsection{Aliasing}

For many compiler optimizations, ranging from simply holding a value in a
register to the parallel execution of a loop, it is necessary to determine
whether two distinct lvalues designate distinct objects.  If the
objects are not distinct, the lvalues are said to be {\em aliases}.  It is
aliasing through pointers that presents the greatest difficulty, because
there is often not enough information available within a single function,
or even within a single compilation unit, to determine whether two
pointers can point to the same object.  Even when enough information is
available, this analysis can require substantial time and space.  For
example, it could require an analysis of a whole program to
determine the possible values of a pointer that is a function parameter.

\subsection{Library examples}

Consider how potential aliasing enters into implementations in C of two
Standard C library functions.  There are no restrictions on the use of
\verb/memmove/, and the implementation shown in \Example{memmove} follows
the model
described in the Standard by copying through a temporary array.
(Other approaches are possible, but this one is straightforward and
strictly conforming.)  Since
\verb/memcpy/ cannot be used for copying between overlapping arrays, its
implementation can be a direct copy, as in \Example{memcpy}.
(See the appendix on ``Overlapping objects.'')

\begin{Code}{memmove}{Sample implementation of memmove}
\begin{verbatim}
void *memmove(void *s1, const void *s2, size_t n) {
    char *t1 = s1;
    const char *t2 = s2;
    char *t3 = malloc(n);
    size_t i;
    for(i = 0; i < n; i++) t3[i] = t2[i];
    for(i = 0; i < n; i++) t1[i] = t3[i];
    free(t3);
    return s1;
}
\end{verbatim}
\end{Code}

\begin{Code}{memcpy}{Sample implementation of memcpy}
\begin{verbatim}
void *memcpy(void *s1, const void *s2, size_t n);
    char *t1 = s1;
    const char *t2 = s2;
    while(n-- > 0) *t1++ = *t2++;
    return s1;
}
\end{verbatim}
\end{Code}

Note that the restriction on \verb/memcpy/ is expressed only in its
{\em Description\/} in the Standard, and cannot be expressed directly in
its implementation in C.  While this does allow the source-level
optimization of eliminating the temporary used in \verb/memmove/, it does
not provide for compiler optimization of the resulting single loop.  In
many architectures, it is faster to copy bytes in blocks, rather than one
at a time.  The implementation of \verb/memmove/ uses \verb/malloc/ to
obtain the temporary array, and this guarantees that the temporary is
disjoint from the source and target arrays.  From this a compiler can
deduce that block copies may safely be used for both loops.  The
implementation of \verb/memcpy/, on the other hand, provides the compiler
no basis for ruling out the possibility that, for example, \verb/s1/ and
\verb/s2/ point to successive bytes.  Therefore unconditional use of block
copies does not appear to be safe, and the code generated for the single
loop in \verb/memcpy/ may not be as fast as the code for the loops in
\verb/memmove/.

\subsection{Restricted pointers}

If an aliasing restriction like the one for \verb/memcpy/ could be expressed
in a function definition, then it would be available
to a compiler to facilitate effective pointer alias analysis.  The
preceding discussion suggests the form that the restriction should take.
It should be possible to specify in the declaration of a pointer that it
provides ``exclusive initial access'' to the object to which it points, as
though the pointer were initialized with a call to \verb/malloc/.  Because
it is the unqualified versions of function parameter types that are
compared for type compatibility, it is convenient to specify the
restriction with a type qualifier, spelled \verb/restrict/, on the pointer
type.  The prototype for \verb/memcpy/ in \Example{memcpy0} thus both
expresses the
desired restriction and is compatible with the current prototype.

\begin{Code}{memcpy0}{Restricted pointer prototype for memcpy}
\begin{verbatim}
void *memcpy(void *restrict s1, const void *restrict s2, size_t n);
\end{verbatim}
\end{Code}

\subsection{Design choices}

Given this general concept of restricted pointers, there remain a number
of design choices.  Three of these are discussed in detail in an appendix.
Most such choices may be characterized as a choice between
simplicity and expressive power.  To some, it seems better to
simplify the analysis of restricted pointers by confining their use to the
simplest paradigms.  For example, restricted pointers would be quite
useful even if they could be declared only as function parameters and
if the restricted pointers themselves could not be modified.
This would support what is clearly the
most important paradigm, an alias-free function call interface in C,
analogous to that in Fortran.  To others, it seems better
to support the expression of aliasing restrictions in as many paradigms as
feasible.  This would be helpful in converting existing programs to
use restricted pointers, and would allow more freedom of style in new
programs.

The definition given in section 3 favors the second view.
It allows restricted pointers to be modifiable, to
be members of structures and elements of arrays, and to be ``strongly
scoped,'' in the sense that a restricted pointer declared in a nested
block makes a non-aliasing assertion only within that block.

\section{Formal definition of restrict}

What follows are proposed additions to the document
{\em International Standard Programming Languages --- C (ISO/IEC 9899:1990(E))}.

\subsection*{Keywords [ISO \S 6.1.1]}

{\em Add a keyword:\/} {\bf restrict}

\subsection*{Type Qualifiers [ISO \S 6.5.3]}

\subsubsection*{Syntax}

{\em Add a type-qualifier:} {\bf restrict}

\subsubsection*{Constraints}

{\em Add a constraint:}

Types other than pointer types derived from object or incomplete types
shall not be restrict-qualified.

\subsubsection*{Semantics}

{\em Add the following text after line 22.}

Let \verb/D/ be a declaration of an ordinary identifier that provides a
means of designating an object \verb/P/ as a restrict-qualified pointer.

If \verb/D/ appears inside a block and does not have storage-class
\verb/extern/, let \verb/B/ denote the block.
If \verb/D/ appears in the list of parameter declarations of a function
definition, let \verb/B/ denote the associated block.
Otherwise, let \verb/B/ denote the block of \verb/main/ (or the
block of whatever function is called at program startup, in a freestanding
environment).

In what follows, a pointer expression \verb/E/ is said to be {\em based\/} on
object \verb/P/ if (at some sequence point in the execution of \verb/B/
prior to the evaluation of \verb/E/) modifying \verb/P/ to point to a copy of
the array object into which it formerly pointed would change
the value of \verb/E/.
(In other words, \verb/E/ depends on the value of \verb/P/ itself rather than
on the value of an object referenced indirectly through \verb/P/.
For example, if identifier \verb/p/ has type \verb/(int **restrict)/,
then the pointer expressions \verb/p/ and \verb/p+1/ are based on
the restricted pointer object designated by \verb/p/, but the pointer
expressions \verb/*p/ and \verb/p[1]/ are not.  Note that
``based'' is defined only for expressions with pointer types.)

During each execution of \verb/B/,
let \verb/O/ be the array object that is determined dynamically
by all references through pointer expressions based on \verb/P/.
Then {\em all\/} references to values
of \verb/O/ shall be through pointer expressions based on \verb/P/.
Furthermore, if \verb/P/ is assigned the value of a pointer expression
\verb/E/ that is based on another restricted pointer object \verb/P2/,
associated with block \verb/B2/, then either the execution of \verb/B2/
shall begin before the execution of \verb/B/, or the execution of
\verb/B2/ shall end prior to the assignment.
If these requirements are not met, then the behavior is undefined.

Here an execution of \verb/B/ means that portion of the
execution of the program during which storage is guaranteed to be reserved
for an instance of an object that is associated with \verb/B/ and has
automatic storage duration.  A reference to a value means either an access
to or a modification of the value.
During an execution of \verb/B/, attention is confined to those
references that are actually evaluated (this excludes references that
appear in unevaluated expressions, and also excludes references that
are ``available,'' in the sense of employing visible identifiers,
but do not actually appear in the text of \verb/B/).

A translator is free to ignore any or all aliasing implications of uses of
\verb/restrict/.


\section{Examples}

\subsection{File scope restricted pointers}

A file scope restricted pointer is subject to very strong restrictions.
It should point into a single array object for the duration of the program.
That array object may not be referenced 
both through the restricted pointer and through either its
declared name (if it has one) or another restricted pointer.
Because of these restrictions, references through the pointer
can be optimized as effectively as references to a file scope array
through its declared name.
File scope restricted pointers are therefore useful for providing
access to dynamically allocated global arrays.
In \Example{extern-name+restr}, a compiler can deduce from
the restrict qualifiers that there is no potential aliasing
among the names \verb/a/, \verb/b/, and \verb/c/.
Notice how the single block of allocated storage is ``subdivided''
into two unique arrays in \verb/init/.

\begin{Code}{extern-name+restr}{File scope restricted pointer}
\begin{verbatim}
float *restrict a, *restrict b;
float c[100];

void init(int n) {
    float *t =  malloc(2 * n * sizeof(float));
    a = t;      /* a refers to 1st half. */
    b = t + n;  /* b refers to 2nd half. */
}
\end{verbatim}
\end{Code}

\subsection{Function parameters}

Restricted pointers are also very useful
as pointer parameters of a function.  In the function \verb/f3/ in
\Example{extern-unrestr}, it is possible for a compiler to infer that
there is no aliasing of modified objects, and so to optimize the loop
aggressively.  Upon entry to \verb/f3/, the restricted pointer
\verb/a/ must provide exclusive access to its associated array.
In particular, within \verb/f3/ neither \verb/b/ nor
\verb/c/ may point into the array associated with \verb/a/,
because neither is assigned a pointer value based on \verb/a/.
For \verb/b/, this is evident from the const-qualifier in its
declaration, but for \verb/c/, an inspection of the body of \verb/f3/
is required.

\begin{Code}{extern-unrestr}{Restricted pointer function parameters}
\begin{verbatim}
float x[100];
float *c;

void f3(int n, float *restrict a, float *const b) {
    int i;
    for ( i = 0; i < n; i++ )
        a[i] = b[i] + c[i];
}
void g3(void) {
    float d[100], e[100];
    c = x; f3(100,   d,    e); /* Behavior defined.   */
           f3( 50,   d, d+50); /* Behavior defined.   */
           f3( 99, d+1,    d); /* Behavior undefined. */
    c = d; f3( 99, d+1,    e); /* Behavior undefined. */
           f3( 99,   e,  d+1); /* Behavior defined.   */
}
\end{verbatim}
\end{Code}

Two of the calls shown in \verb/g3/ result in aliasing that is
inconsistent with the \verb/restrict/ qualifier, and their
behavior is undefined.  Note that it is permitted for \verb/c/ to point
into the array associated with \verb/b/.
Note also that, for these purposes, the ``array'' associated
with a particular pointer means only that portion of an array object
which is actually referenced through that pointer.

For a similar example in which \verb/c/ is another parameter instead
of a file scope array, see ``Aliasing of unmodified objects'' in the
appendix on ``Discussion of design choices.''

\subsection{Block scope}

A block scope restricted pointer makes an aliasing assertion
that is limited to its block.  This seems more natural than
allowing the assertion to have function scope.  It allows
local assertions that apply only to key loops, for example.
It also allows equivalent assertions to be made when
inlining a function by converting it into a macro.
In \Example{inline}, the original restricted pointer parameter
is represented by a block scope restricted pointer.

\begin{Code}{inline}{Macro version of f3}
\begin{verbatim}
float x[100];
float *c;

#define f3(N, A, B)                                    \
{   int n = (N);                                       \
    float *restrict a = (A);                           \
    float *const    b = (B);                           \
    int i;                                             \
    for ( i = 0; i < n; i++ )                          \
        a[i] = b[i] + c[i];                            \
}
\end{verbatim}
\end{Code}


\subsection{Members of structures}

A restricted pointer member of a structure makes an aliasing
assertion, and the scope of that assertion is the scope of the
ordinary identifier used to access the structure.
Thus although the structure type is declared at file scope
in \Example{struct-member}, the assertions made
by the declarations of the parameters of \verb/f4/
have block (of the function) scope.

\begin{Code}{struct-member}{Restricted pointers as members of a structure}
\begin{verbatim}
struct t {     /* Restricted pointers assert that    */
    int n;     /* members point to disjoint storage. */
    float *restrict p;
    float *restrict q;
};

void f4(struct t r, struct t s) {
    /* r.p, r.q, s.p, s.q should all point to    */
    /* disjoint storage during each execution of f4. */
    /* ... */
}
\end{verbatim}
\end{Code}

\subsection{Type definitions}

A \verb/restrict/ qualifier in a type definition makes an aliasing
assertion when the typedef name is used in the declaration of
an ordinary identifier that provides access to an object.
As with members of structures, it is the scope of the latter
identifier, not the scope of the typedef name, that determines the
scope of the aliasing assertion.

\subsection{Expressions based on restricted pointers}

In \Example{eg_based}, the restricted pointer parameter \verb/p/ is
potentially adjusted to point into a copy of its original array of two
structures.  By definition, a subsequent pointer expression is said to
be based on \verb/p/ if and only if its value is changed by this
adjustment.  In the comment, the values of the pointer expressions in
the first column are changed by this adjustment, and so those
expressions are based on \verb/p/.  The values of the pointer
expressions in the second column are not changed by the adjustment, and
so those expressions are not based on \verb/p/.  This can be verified
by adding appropriate print statements for the expressions, and
comparing the values produced by the two calls of \verb/f5/ in
\verb/main/.

It is important to note that the definition of ``based on'' applies to
expressions that rely on im\-ple\-men\-ta\-tion-defined behavior.  This is
illustrated in this example, which assumes that the casts \verb/(int)/
followed by \verb/(struct t *)/ give the original value.

\begin{Code}{eg_based}{Pointer expressions based on p}
\begin{verbatim}
#include <stdlib.h>
#include <string.h>

struct t { int *q; int i; } a[2] = { /* ... */ };

void f5(struct t *restrict p, int c)
{
    struct t *q;
    int n;
    if(c) {
        struct t *r;
        r = malloc(2*sizeof(*p));
        memcpy(r, p, 2*sizeof(*p));
        p = r;
    }
    q = p;
    n = (int)p;
    /* - - - - - - - - - - - - - - - - - - - - - - -
      Pointer expressions     Pointer expressions
      based on p              not based on p

      p                       p -> q
      p + 1                   p[1] . q
      &p[1]                   &p
      &p[1] . i
      &p->q
      q                       q -> q
      ++q
      (char *)p               (char *)(p -> i)
      (struct t *)n           ((struct t *)n) -> q
    - - - - - - - - - - - - - - - - - - - - - - - */
}

main() {
    f5(a, 0);
    f5(a, 1);
}
\end{verbatim}
\end{Code}

\subsection{Assignments between restricted pointers}

Let us say that one restricted pointer is ``newer'' than another if the
block with which the first is associated begins execution after the
block associated with the second.  Then the formal definition allows a
newer restricted pointer to be assigned a value based on an older
restricted pointer.  This allows, for example, a function with a
restricted pointer parameter to be called with an argument that is a
restricted pointer.

Conversely, an older restricted pointer may be assigned a value based
on a newer restricted pointer only after execution of the block
associated with the newer restricted pointer has ended.  This allows,
for example, a function to return the value of a restricted pointer
that is local to the function, and the return value then to be assigned
to another restricted pointer.

The behavior of a program is undefined if it contains an assignment
between two restricted pointers that does not fall into one of these
two categories.  Some examples are given in \Example{eg_assign}.

\begin{Code}{eg_assign}{Assignments between restricted pointers}
\begin{verbatim}
int *restrict p1, *restrict p2;

void f6(int *restrict q1, int *restrict q2)
{
    p1 = p2;     /* Behavior undefined. */
    p1 = q1;     /* Behavior undefined. */
    q1 = q2;     /* Behavior undefined. */
    {
        int *restrict r1, *restrict r2;
        ...
        r1 = r2; /* Behavior undefined. */
        q1 = r1; /* Behavior undefined. */
        p1 = r1; /* Behavior undefined. */
        ...
    }
}
\end{verbatim}
\end{Code}


\subsection{Assignments to unrestricted pointers}

This proposal permits assignment of the value of a restricted pointer
to an unrestricted pointer, as in \Example{unrestr1}.

\begin{Code}{unrestr1}{Assigning restricted to unrestricted pointers}
\begin{verbatim}
void f7(int n, float *restrict r, float *restrict s) {
    float *p = r, *q = s;
    while(n-- > 0)
        *p++ = *q++;
}
\end{verbatim}
\end{Code}

If a compiler tracks pointer values, it should be able to optimize the
loop as effectively as if the restricted pointers \verb/r/ and \verb/s/
were used directly.

More complicated ways of combining restricted and unrestricted pointers
are  less likely to be effective because they are more difficult for a
compiler to analyze.
As always, a programmer concerned about performance must adapt his
style to the capabilities of available compilers.  A conservative
approach would be to avoid using both restricted and unrestricted
pointers in the same function.


\subsection{Ineffective uses of type qualifiers}

Except where specifically noted in the formal definition, the
\verb/restrict/ qualifier behaves in the same way as \verb/const/ and
\verb/volatile/.  In particular, note that it is not a constraint
violation for a function return type or the {\em type-name\/} in a cast
to be qualified, but the qualifier has no effect because function call
and cast expressions are not lvalues.  Thus the presence of the
\verb/restrict/ qualifier in the declaration of \verb/f8/ in
\Example{return-type} makes no assertion about aliasing in functions
that call \verb/f8/.  Similarly, the two casts make no assertion about
aliasing of the references through the pointers \verb/p/ and \verb/r/.

\begin{Code}{return-type}{Qualified function return type and casts}
\begin{verbatim}
float *restrict f8(void)  /* No assertion about aliasing. */
{
    extern int i, *p, *q, *r;

    r = (int *restrict)q; /* No assertion about aliasing. */

    for(i = 0; i < 100; i++)
        *(int *restrict)p++ =  r[i];   /* No assertion    */
                                       /* about aliasing. */
    return p;
}
\end{verbatim}
\end{Code}

\subsection{Constraint violations}

It is a violation of the constraint in ISO \S 6.5.3
(of the Standard as modified above)
to restrict-qualify an object
type which is not a pointer type, or to restrict-qualify a pointer to a
function.

\begin{Code}{non-ptr}{Restrict cannot qualify non-pointer object types}
\begin{verbatim}
    int restrict x;   /* Constraint violation. */
    int restrict *p;  /* Constraint violation. */
\end{verbatim}
\end{Code}

\begin{Code}{ptr-to-function}{Restrict cannot qualify pointers to functions}
\begin{verbatim}
float (*restrict f9)(void); /* Constraint violation. */
\end{verbatim}
\end{Code}

\cleardoublepage

\section{Appendix: Overlapping objects}

The restriction in the {\em Description\/} of \verb/memcpy/ prohibits
copying between ``overlapping objects.''  An interpretation from
X3J11 and WG14 in response to DR \#042, X3J11 92-001, clarified what is
meant by ``objects'' in this context.  The following quotation from
that defect report provides a background for the notion of
an ``object that is determined dynamically'' that appears
in the formal definition of \verb/restrict/.

\begin{quote}
From subclause 3.14, an object is ``a region of data storage \ldots
Except for bit-fields, objects are composed of contiguous sequences
of one or more bytes, the number, order, and encoding of which are
either explicitly specified or implementation-defined \ldots''
\end{quote}

\begin{Code}{memcpy1}{Memcpy between rows of a matrix}
\begin{verbatim}
    void f1(void) {
        extern char a[2][N];
        memcpy(a[1], a[0], N);
    }
\end{verbatim}
\end{Code}

\begin{quote}
Therefore, the ``objects'' referred to by subclause 7.11.2.1 are exactly the
regions of data storage pointed to by the pointers and dynamically
determined to be of \verb/N/ bytes in length (i.e. treated as an array of
\verb/N/ elements of character type).

a) So, no, the objects are not ``the largest objects into which the
arguments can be construed as pointing''.

b) In \Example{memcpy1}, the call to \verb/memcpy/ has defined behavior.

c) The behavior is defined because the pointers point into
different (non-overlapping) objects.
\end{quote}

\begin{Code}{memcpy2}{Memcpy between halves of an array}
\begin{verbatim}
    void f2(void) {
        extern char b[2*N];
        memcpy(b+N, b, N);
    }
\end{verbatim}
\end{Code}

\begin{quote}
a)  Yes, for \verb/memcpy/, a contiguous sequence of elements within
an array can be regarded as an object in its own right.

b)  The objects are not the smallest contiguous sequence of bytes that
can be construed; they are exactly the regions of data storage starting
at the pointer and of \verb/N/ bytes in length.

c)  Yes, the non-overlapping halves of array \verb/b/ can be regarded as
objects in their own rights.

d)  The behavior (in \Example{memcpy2}) is defined.

\ldots

Length is determined by ``various methods.''  For strings in which all
elements are accessed, length is inferred by null byte termination.
For \verb/mbstowcs/, \verb/wcstombs/, \verb/strftime/, \verb/vsprintf/,
\verb/sscanf/, \verb/sprintf/, and all
other similar functions, it was the intent of the standard that the
rules in subclause 7.11.1 be applicable by extension (i.e., the objects and
lengths are similarly dynamically determined).
\end{quote}

\clearpage

\section{Appendix: Discussion of design choices}

\subsection{Contiguity}

A restricted pointer points to an associated object that is determined
dynamically.  When all references, both direct and indirect, through a
restricted pointer comprise a contiguous sequence of bytes, then the
associated object is exactly that sequence.  Otherwise, the object
consists of both the referenced bytes and those unreferenced bytes that
fall between any two referenced bytes.

This convention is consistent with the specification noted above, that
``except for bit-fields, objects are composed of contiguous sequences
of one or more bytes.''  It is also consistent with the notions of
objects and argument association in Fortran 77.  Thus, in environments
that support mixed-language programming, restricted pointer parameters
can be used in C prototypes for functions defined in Fortran, and also
in definitions of C functions that are called from Fortran.

Note that an implementation is free to support restricted pointers to
non-contiguous sets of bytes as an extension.  Such support is not
mandated, however, because the need for it does not seem compelling,
and it could inhibit optimizations for architectures that cannot load
and store single bytes or that have software-managed caches.  Note that
such an extension might be useful in implementation-defined calling
conventions between C and Fortran 90, because Fortran 90 permits
arguments that are non-contiguous sets of array elements.

\subsection{Aliasing of unmodified objects}

Comparison with Fortran raises an issue concerning
aliasing of unmodified objects, as illustrated in \Example{rstr-modif}.
Knowing that parameter \verb/a/ provides exclusive access to the array
into which it points is sufficient to allow the loop in \verb/f10/ to
be vectorized or executed in parallel.  Knowing that \verb/b/ and \verb/c/
are not used to access overlapping portions of a single array allows no
additional optimizations, and so, in principle, there is no need to
restrict-qualify \verb/b/ and \verb/c/.

\begin{Code}{rstr-modif}{Aliasing matters only for modified objects}
\begin{verbatim}
void f10(int n, float *restrict a, float *b, float *c) {
    int i;
    for ( i = 0; i < n; i++ )
        a[i] = b[i] + c[i];
}
\end{verbatim}
\end{Code}

But, as a practical matter, it is easier for a compiler to analyze
functions in which all pointer parameters are restrict-qualified.
This suggests that the semantics of the qualifier should be defined
so that one can restrict-qualify all three pointer parameters of \verb/f10/
and still make calls of the form \verb/f10(x,y,y)/.  This would be analogous
to the aliasing semantics of Fortran dummy arguments.

The simplest way of doing this (proposed in Draft 1 of this report)
is to allow aliasing through two restrict-qualified pointers provided
the referenced objects are not modified.
Unfortunately, if those objects are themselves pointers (i.e., there are
two levels of indirection), this aliasing can inhibit optimization, even
if the secondary pointers are also restrict-qualified and used to modify
the objects to which they, in turn, refer.
See X3J11.1/93-040 for examples.

In the final analysis, it did not seem possible
to permit aliasing of unmodified objects,
have effective assertions for multiple levels of indirection,
and still keep the semantics relatively simple.

It was decided to drop the special treatment of unmodified objects,
largely because the practical effect is quite small.
First, as noted, the extra qualifiers are not needed in principle,
though they may be useful for specific compilers.
Second, in these cases, it is also useful, and might be sufficient,
to const-qualify \verb/b/ and \verb/c/, because this gives a compiler
enough aliasing information in the parameter declarations alone
to optimize \verb/f10/ (see the discussion of \Example{extern-unrestr}).
Finally, even if a specific compiler requires all three restrict
qualifiers to give the desired optimization, it is most unlikely
that their use would give unexpected results for a call such as
\verb/f10(x,y,y)/, even though its behavior is technically undefined. 
Such use may therefore be justified in particular cases, as are
other instances of undefined or implementation-defined behavior,
such as assigning to one member of a union and then referring to another.

\subsection{Linked lists}

Operations on data contained in the items of a linked list are
difficult to optimize, particularly for vector or parallel execution.
Because potential aliasing is not the only difficulty, it
is unlikely that the use of restricted pointers in this context will
make much difference with currently available compilers.
Nevertheless, as the use of parallel architectures becomes more
widespread, their compilers may well be more ambitious in this area.
With this in mind, the examples in \Example{eg_list1} illustrate how to use the
\verb/restrict/ and \verb/const/ qualifiers to make assertions that could,
in principle, enable effective optimizations.

First note that restricted pointers cannot, in general, be used  
for link pointers in portions of the program that modify the lists.
Thus in \Example{eg_list1}, the assignments to
\verb/next/ and \verb/head/ would give undefined behavior if they
were restrict qualified.

\begin{Code}{eg_list1}{Operations on the structure of a linked list}
\begin{verbatim}
struct t { struct t *next; float x; } *head, *item;

void modify_links()
    /* Add a list item at the beginning. */
    item -> next = head; head = item;

    /* Add a list item as the second item. */
    item -> next = head -> next; head -> next = item;

    /* Delete second list item. */
    head -> next = head -> next -> next;

    /* Delete first list item. */
    head = head -> next;
}
\end{verbatim}
\end{Code}

In contrast, in functions in which the structure of the
lists is constant, this can be asserted by using a combination
of the \verb/restrict/ and \verb/const/ qualifiers.  Note that, as in
\Example{eg_list2}, this requires a second structure type,
and a cast from the original to the new type. 
The comments describe an optimization that allows
parallel execution of the second loop.
Alternatively, the second loop could be fused with the first,
so that both operations are performed during a single walk.
The latter optimization is likely to be beneficial on any architecture. 

\begin{Code}{eg_list2}{Operations on the values in a linked lists}
\begin{verbatim}
struct t { struct t *next; float x; };
struct rt { struct rt *const restrict next; float x; };

void modify_values(struct t *head) {
    /* Assert that links will not change. */
    struct rt *const restrict rhead = (struct rt *)head;

    /* Need modifiable unrestricted pointer to walk list. */
    struct rt *this;

    /* Can build a cache of link addresses. */
    for(this = rhead; this; this = this -> next) {
        this -> x += 1;
    }

    /* Can use cached addresses to execute in parallel. */
    for(this = rhead; this; this = this -> next) {
        this -> x *= 2;
    }
}
\end{verbatim}
\end{Code}

Unfortunately, there is a subtle problem with this approach.
If there is a function call between the two loops that has
\verb/rhead/ as a parameter, then there should be a guarantee
that the cached links are not changed during the execution of the called
function.  The problem is that there is nothing to prevent
the function from modifying a link via
\begin{quote}
\verb/*(struct rt *restrict *)&(rhead -> next) = .../
\end{quote}
(assuming for the sake of argument that the structures on the list
were dynamically allocated as an array of structures).
To make the aliasing assertions effective
would require forbidding this sort of modification.  This might be done
be extending the full semantics of the \verb/const/ qualfier to include
objects designated as const-qualified by a restricted pointer, as well
as objects that are const-qualified by their definitions.  (This
extension is not part of the current proposal.)

\clearpage

\section{Appendix: Array syntax and qualified parameters}

By ISO \S 6.7.1,
a declaration of a function parameter as ``array of {\em type}''
is adjusted to ``pointer to {\em type}.''
Thus the two prototypes in \Example{param-adjust} for \verb/f11/
are compatible.

\begin{Code}{param-adjust}{Equivalent parameter declarations}
\begin{verbatim}
void f11(int n, float a[][100], float b[][100]);
void f11(int n, float (*a)[100], float (*b)[100]);
\end{verbatim}
\end{Code}

In either case, \verb/a/ and \verb/b/ are pointers used to access
their respective two-dimensional arrays, but the first form more clearly
conveys the rank of the arrays.  It is therefore unfortunate that only the
second form allows the pointers to be qualified, e.g., by \verb/restrict/.

This suggests an extension of the syntax to allow one or more type
qualifiers to appear within the ``array of'' type derivation for a
function parameter declared to have array type.  The declaration is
then adjusted to the analogously qualified pointer type.

\begin{Code}{rstr-no-extent}{Restricted version of f11}
\begin{verbatim}
void f11(int n, float a[restrict][100], float b[restrict][100])
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < 100; j++)
           a[i][j] = b[i][j];
}

void g11(int m, int k, float p[][100]) {
    f11(m, p, p+k); /* Defined if and only if m <= k. */
}
\end{verbatim}
\end{Code}

This extension would be even more convenient in the presence of a
variable length array extension, that would allow another parameter
to be used in an array size expression.  In \Example{rstr-extent},
the compiler, or code reviewer, can use the information in the
prototype alone to deduce that the first call of \verb/f12/ in \verb/g12/
is defined, but the second call is potentially undefined (depending upon
which elements of the arrays \verb/f12/ actually  references).

\begin{Code}{rstr-extent}{Restrict and variable length arrays}
\begin{verbatim}
void f12(int m, int n, float a[restrict m][n],
                       float b[restrict m][n]);

void g12(int n, float p[][n]) {
        f12(10, n, p, p+10); /* Defined behavior. */
        f12(20, n, p, p+10); /* Potential undefined behavior. */
}
\end{verbatim}
\end{Code}

For consistency, the extension would apply to all type qualifiers.
The following changes to the Standard would be required for this extension.

\subsection*{Declarators [ISO \S 6.5.4]}

\subsubsection*{Syntax}

{\em Allow an optional {\em type-qualifier-list} in the third form
of direct-declarator:}

{\em direct-declarator\/}
\verb/[/ {\em type-qualifier-list} \( _{opt} \)
{\em constant-expression} \( _{opt} \) \verb/]/

\subsection*{Array Declarators [ISO \S 6.5.4.2]}

\subsubsection*{Constraints}

{\em Add a constraint:}

Type qualifiers shall appear preceding or in place of a size expression
only in a declaration of a function parameter of array type, and then only
in the outermost array type derivation.

\subsection*{Function Definition [ISO \S 6.7.1]}

\subsubsection*{Semantics}

{\em Modify lines 23-24 to read:}

\ldots A declaration of a parameter as ``array of {\em type}'' shall be
adjusted to ``qualified pointer to {\em type}'' (where the type qualifiers
are those specified within the square brackets of the array type derivation),
\ldots

\clearpage

\section{Appendix: Comparison with noalias}

The following is an overview of the differences
between \verb/restrict/ and the previously proposed \verb/noalias/.

The X3J11 committee attempted to solve the aliasing problem in C by
introducing a new type qualifier \verb/noalias/.  That effort failed
because of technical problems with the proposed semantics of \verb/noalias/.
This restricted pointer proposal is different in many ways.
\begin{itemize}
\item
Only pointers can be declared to be restricted.
In the \verb/noalias/ proposal, all objects were permitted to be declared
noalias-qualified.
\item
It is the declaration of the restricted pointer that makes the
aliasing assertions, while it was the noalias-qualified lvalue
that made the aliasing assertions.
\item
A restricted pointer can be an alias with an unrestricted pointer,
whereas a pointer to a noalias-qualified type was guaranteed to be
completely alias free.
\item
The
proposed semantics of \verb/noalias/ defined an alternate execution path
in which virtual objects were created and later synchronized with the
original object.  No alternate execution path is defined for
restricted pointers.  The proposed semantics for restricted pointers
merely permit the optimizer to statically analyze restricted pointers.
\item
A block scope restricted pointer only makes assertions on
the containing scope.  In the \verb/noalias/ proposal, a block scope
noalias-qualified object made assertions that affected the entire
containing function.
\item
A pointer to a noalias-qualified type made no aliasing assertion
if it was a member of a structure (because identifiers designating
members of structures were not ``handles'').  A restricted pointer
member of a structure does make an aliasing assertion.
\end{itemize}

\cleardoublepage

\end{document}
