JTC1/SC22/WG14
N867
Document number: WG14 N867 (J11/99-002)
Title: Restrict and array parameters
Author: Bill Homer
Date: 10-Jan-99
URL: http://reality.sgi.com/homer_craypark/c9x/n867.txt
http://reality.sgi.com/homer_craypark/c9x/n867.html
1 ---------- Summary ------------------------------------------------
2
3 This document addresses an optimization issue, from PC-UK0118, for
4 array arguments to functions.
5
6 ---------- Description of the issue -------------------------------
7
8 Consider a function of the form:
9
10 void f(int n, double *a, const double *b)
11 {
12 int i;
13 ...
14 for(i=0; i<n; i++)
15 a[i] += b[i];
16 }
17
18 It would be a significant advantage on some systems for the
19 translator to initiate, at the beginning of the function,
20 prefetches or loads of the arrays that will be referenced through
21 second and third parameters. Unfortunately, under the FCD, this
22 presents problems.
23
24 First, a translator must determine the number of elements to load.
25 In this simple example, it is easy to see that the number of
26 elements is n (or greater, depending on the parts of the function
27 that are not shown), but in general this is not so easy to
28 determine, particularly if some or all of the operations on the
29 arrays are hidden in function calls (e.g., to BLAS or LAPACK
30 functions).
31
32 Second, a translator might have to generate runtime checks to be
33 sure that n is greater than zero, and that the second and third
34 arguments are not null (because, for example, if a call takes a
35 path through the function that does not use a pointer parameter,
36 it might supply a null value for the corresponding argument).
37
38 What is needed is a means by which the programmer can assert that a
39 pointer argument is non-null and can specify the number of elements
40 to which the argument is guaranteed to provide access. One way to
41 do this would be to add these assertions to the meaning of what is
42 currently an equivalent prototype:
43
44 void f(int n, double a[n], const double b[n])
45
46 But this might break some existing programs (programs which use
47 constant expressions for the size expressions, or which use the vla
48 extension already available from some translators).
49
50 What follows is an alternative approach that addresses the issue
51 but does not break any existing programs.
52
53 ---------- Description of the proposed change ----------------------
54
55 The proposed change is to extend the syntax to allow a type
56 qualifier to precede the size expression in a parameter declaration
57 that declares an array. If such a type qualifier appears, then the
58 corresponding actual argument shall evaluate to a pointer
59 expression that provides access to an array of (at least) n
60 elements. Furthermore, when the type of the parameter is adjusted
61 to a pointer type, the type qualifiers apply to that type.
62
63 For example, in the function f() above, because its second and
64 third parameters are not themselves modified, its prototype could
65 be written:
66
67 void f(int n, double a[const n], const double b[const n])
68
69 Furthermore, if the programmer knows that there is no overlap
70 between arrays a and b in any of the calls of f(), then he can
71 assert that fact by using the restrict qualifier instead of (or in
72 addition to) the const qualifier:
73
74 void f(int n, double a[restrict n], const double b[restrict n])
75
76 In either case, the translator can infer from the prototype alone
77 that the arrays can be safely preloaded using the declared extents.
78
79 ---------- Proposed edits to FCD -----------------------------------
80
81 6.7.5 Declarators, Syntax, #1
82
83 === Change the third and fourth forms of direct-declarator from:
84
85 < direct-declarator [ assignment-expression-opt ]
86 < direct-declarator [ * ]
87
88 === to:
89
90 > direct-declarator [ type-qualifier-list-opt
91 > assignment-expression-opt ]
92 > direct-declarator [ type-qualifier-list-opt * ]
93
94 6.7.5.2 Array declarators, Constraints
95
96 === Append to #1:
97
98 > The optional type qualifiers preceding the expression or
99 > the * shall appear only in a declaration of a function
100 > parameter with an array type, and then only in the outermost
101 > array type derivation.
102
103 6.7.5.2 Array declarators, Semantics
104
105 === Append to #3:
106
107 > See 6.7.5.3, Function declarators, for the meaning of the
108 > optional type qualifiers.
109
110 6.7.5.3 Function declarators (including prototypes), Semantics
111
112 === Change from:
113
114 [#6] A parameter type list specifies the types of, and may
115 declare identifiers for, the parameters of the function.
116 < A declaration of a parameter as ``array of type'' shall be
117 < adjusted to ``pointer to type'', and a declaration of a
118 parameter as ``function returning type'' shall be adjusted
119 to ``pointer to function returning type'', as in 6.3.2.1.
120
121 === to:
122
123 [#6] A parameter type list specifies the types of, and may
124 declare identifiers for, the parameters of the function.
125 > A declaration of a parameter as ``array of type'' shall
126 > be adjusted to ``qualified pointer to type'', where the
127 > type qualifiers, if any, are those specified within the
128 > square brackets of the array type derivation. If a size
129 > expression follows such a type qualifier, then, for each
130 > call of the function, the value of the corresponding actual
131 > argument shall provide access to the first element of an
132 > array with at least that many elements. A declaration of a
133 parameter as ``function returning type'' shall be adjusted
134 to ``pointer to function returning type'', as in 6.3.2.1.