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.