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