ISO/ IEC JTC1/SC22/WG14 N682


                             C9X Revision Proposal
                             =====================

     WG14/N682   (J11/97-045)                WG14/N682   (J11/97-045)
     
     Title: Suggested edits for C9X Draft 9 section 6.5.3
     Author: Tom MacDonald and Bill Homer
     Author Affiliation: Cray Research, an SGI company
     Postal Address:     Cray Research Park
                         655F Lone Oak Drive
                         Eagan,  MN  55121
                         USA
     E-mail Address:     tam@cray.com      homer@cray.com
     Document Number:    WG14/N682   (J11/97-045)
     Telephone Number:   +1-612-683-5818
     Fax Number:         +1-612-683-5307
     Sponsor: J11
     Date: 08-MAY-1997
     Proposal Category:
        XX Editorial change/non-normative contribution
        __ Correction
        __ New feature
        __ Addition to obsolescent feature list
        __ Addition to Future Directions
        __ Other (please specify)  Change of current behavior
     Area of Standard Affected:
        __ Environment
        XX Language
        __ Preprocessor
        __ Library
           __ Macro/typedef/tag name
           __ Function
           __ Header
        __ Other (please specify)  ______________________________
     Prior Art:  N/A
     Target Audience:  all C programmers
     Related Documents (if any):  NONE
     Proposal Attached: XX Yes   __ No, but what's your interest?

     Abstract: Edits for C9X Draft section 6.5.3

     ======================= Cover sheet ends here ==============

The intent is to improve the flow of the section.

1.  Move the paragraphs in 6.5.3 that define the semantics of restrict
    (#6 through #11 in c9xd9-pre3) into a new subsection 6.5.3.1,
    entitled "Formal definition of restrict", and place this new
    subsection after the first two examples.

2.  In place of those five moved paragraphs, put the following new
    paragraph (so it will follow the paragraph about volatile,
    #5 in c9xd9-pre3):

        An object that is referenced through a restrict-qualified
        pointer has a special association with that pointer.  This
        association, defined in 6.5.3.1 below, requires that all
        references to that object shall use, directly or indirectly,
        the value of that pointer.  For example, a statement that
        assigns a value returned by malloc to a single pointer
        establishes this association between the allocated object and
        the pointer.  The intended use of the restrict qualifier
        (like the register storage class) is to promote optimization,
        and deleting all instances of the qualifier from a conforming
        program does not change its meaning (i.e., observable behavior).

3.  Revise and add to the existing examples 3 and 4, and move them into
    a new Examples section following the new section 6.5.3.1.
    That section should read:

    Examples

    3.  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.

    4.  The function parameter declarations

            void f(int n, int * restrict p, int * restrict q) {
                while ( n-- > 0 ) *p++ = *q++;
            }

        assert that, during each execution of the function, if an
        object is referenced through one of the pointer parameters,
        then it is never referenced through the other.

        The benefit of the restrict qualifiers is that they enable
        a translator to make an effective dependence analysis of
        function f without examining any of the calls of f in the
        program.  The cost is that the programmer must examine all
        of those calls to ensure that none give undefined behavior.
        For example, the second call of f in g has undefined
        behavior because each of d[1] through d[49] is referenced
        through both p and q.

           void g(void) {
               extern float d[100];
               f(50, d+50, d); /*   defined behavior */
               f(50,  d+1, d); /* undefined behavior */
           }

    5.  The function parameter declarations
                
            void h(int n, int * const restrict p,
                   int * const q, int * const r) {
                int i;
                for ( i=0; i<n; i++ ) {
                    p[i] = q[i] + r[i];
                }
            }
        
        show how const can used in conjunction with restrict.
        The const qualifiers imply, without the need to examine the
        body of h, that q and r cannot become based on p.  The fact
        that p is restrict-qualified therefore implies that an
        object referenced through p is never referenced through
        either of q or r.  This is the precise assertion required
        to optimize the loop.  Note that a call of the form
        h(100, a, b, b) has defined behavior, which would not be
        true if all three of p, q, and r were restrict-qualified.

    6.  The rule limiting assignments between restricted
        pointers does not distinguish between a function call
        and an equivalent nested block.  With one exception,
        only "outer-to-inner" assignments between
        restricted pointers declared in nested blocks
        have defined behavior.

           {  int * restrict p1;
              int * restrict q1;
              p1 = q1;                   /* undefined behavior */
              {  int * restrict p2 = p1; /*   defined behavior */
                 int * restrict q2 = q1; /*   defined behavior */
                 p1 = q2;                /* undefined behavior */
                 p2 = q2;                /* undefined behavior */
              }
            }
        
        The exception allows the value of a restricted pointer
        to be carried out of the block in which it (or, more
        precisely, the ordinary identifier used to designate it)
        is declared when that block finishes execution.  For
        example, this permits new_vector to return a vector.

            typedef struct { int n; float * restrict v; } vector;

            vector new_vector( int n ) {
                vector t;
                t.n = n;
                t.v = malloc(n * sizeof(float));
                return t;
            }

======  End of suggested edits for C9X Draft 9 section 6.5.3  =======
======
======
============ Additional text for the rationale ======================

To see why the specification for the restrict qualifier has to be
so complicated, consider the simplest semantics:

    If an object is ever referenced through a restricted pointer,
    then it must always be referenced through that same pointer.

Though this is clear, it is very limiting.  The only way to reference
an object in more than one function through such a restricted pointer
would be to declare it at file scope.  The specification necessarily
gets more complicated to make restricted pointers useful in other
contexts.

1.  Restricted pointers can be used as both the argument and
    corresponding parameter of a function, but the values of two
    restricted pointer parameters for a function cannot be used to
    form aliases for the same object, either in their associated
    function or in any function called directly or indirectly from
    within their associated function.

    This is the original charter of a Fortran-like semantics for
    function calls.  It requires that, for a restrict qualifier in
    a declaration associated with a block, the effects of the
    qualifier are limited to the execution of that block.  This
    requirement alone brings in much of the complication, and seems
    to require some concept like "based".

2.  A restricted pointer can be a member of a structure or an
    element of an array.

    Otherwise, a structure cannot be used to package a restricted
    pointer with the size of the array to which it points, for example.
    This requires distinguishing between the object designated as a
    restrict-qualified pointer and the ordinary identifier used
    (together with member selection or indexing) to make that
    designation.

3.  Restricted pointers declared in nested blocks are treated
    like parameters of inlined functions.

    This allows a function to be inlined manually with a macro
    (and does not impose any additional implementation costs on
    a translator that inlines functions automatically).
    It requires the specification to speak about blocks in
    general instead of only blocks of functions, and to impose an
    "outer-to-inner" discipline on assignments between restricted
    pointers.

4.  A restricted pointer can be assigned a function return value
    based on a restricted pointer declared in that function.

    This exception to the "outer-to_inner" discipline of the
    previous point is needed for some types of member access
    function, in an object oriented style of programming.  It
    requires only the extra phrase:  "or shall end before the
    assignment".