target

integration into IS ISO/IEC 9899:202y

document history

license

CC BY, see https://creativecommons.org/licenses/by/4.0

1 Problem description

The restrict qualifier is an important corner stone in C’s memory model. It gives implicit guarantees to avoid pointer aliasing as much as possible and contributes much to the relative efficiency of C code compared to programs that are written in similarly structured programming languages.

Unfortunately, the description of this concept in the current C standard is vague and has not been kept in sync with the newer concepts of data dependencies, sequencing (within a single thread) and synchronization (between several threads) that the C standard has refined over the years.

Recently, several attempts have been made to improve this specification. In our view, none of them is satisfactory because they do not attack the fundamental problems.

The start of the current clause (C23) that specifies the semantics of the restrict qualifier reads as follows:

6.7.4.2 Formal definition of restrict

1 Let D be a declaration of an ordinary identifier that provides a means of designating an object P as a restrict-qualified pointer to type T.

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

3 In what follows, a pointer expression E is said to be based on object P if (at some sequence point in the execution of B prior to the evaluation of E) modifying P to point to a copy of the array object into which it formerly pointed would change the value of E.¹⁵³⁾ Note that “based” is defined only for expressions with pointer types.

By its title it is a promise (to provide a formal definition) but it is in fact very delicate mix up of semantic concepts that make it almost impossible to comprehend from the given text. And as a consequence it is not very surprising that after all these years people are still detecting problems.

The text has many problems. In the following we give an unordered list of problems that we detected. It is possible that there are some more that we overlooked.

• What does “means of designating an object P” mean?

• What does “at some sequence point” mean? Why is not general sequencing (or synchronization) considered?

• Expression itself is a grammatical term and has no such thing as a value. Evaluations of expressions have a value, and evaluations are sequenced (or not).

• Does the implicit data dependency between E and P that is used include

  • conversion between pointers and integers,
  • access to representation bytes,
  • IO,
  • dependencies between pointer data and control flow,
  • transfer of information through certain C library channels such as tss_get?

• Why does this only name D the declaration, possibly without an initializer, whereas later for the transfer of values on one hand we need the identifier I (or a member access to the corresponding member) one instance (of possibly many) of the object, and to a specific run-time value that is stored in the instance?

• Why does this talk about a declaration at all, when the restrict qualification of an object is clearly also relevant for objects that have no declaration, but that receive an effective type through store operation?

It is possible that any of these problems could be solvable with some care or even by imposing a specific reading of the text, but seen as a whole, the text is not in a state a center piece of the C standard should be.

2 The underlying model and its intent

There is a clear intent behind the introduction of the restrict qualifier, namely to give programmers better possibilities to deal with aliasing between different pointer targets that might be accessed within the same program block. In particular, if a guarantee is provided to the compiler that accesses to a specific object only happen through one specific pointer value (traced from a unique pointer object when entering into block), many optimization strategies may be applied without changing the semantics of the program. These optimizations include in particular reordering of statements (because there are gurantees of independence) and dead-store elimination (because certain stores then are known to be overwritten before they are ever read).

This primary intent has to be distinguished from the model that is chosen to implement a feature with these properties in the standard. This is where unfortunately the current text fails to provide a clear and concise specification that would integrate well into the terminology, which has much evolved, and for which the text for restrict has not been properly adapted. Our proposal tries to use existing concepts in other clauses of the C standard to provide a sound model:

• the “sequenced before” relation between evaluations within the same thread, including signal handlers
• the “happens before” relation that provides the same but extended to threads,
• the “carries a dependency” relation that models information flow between evaluations.

It has to be noted that all three relations are relations between runtime-features, namely evaluations. They are not necessarily linked to specific lexical features and therefore might be difficult to deduce by a compiler. Therefore an important property of the specification is that

restrict provides guarantees given by the programmer to the compiler

and not the other way around. In particular, the properties that are guaranteed in their generality are not easily deducible since they would need to argue about all possible evaluations of the program block in question. Therefore the only tool at hand in the C standard to describe a violation is UB

Violating the properties induced by restrict qualification has undefined behavior.

So the primary intent of this feature is to ensure that within a block of the program the same object cannot be accessed (and modified) through different access patterns, patterns for which it would not be possible for the compiler to deduce that they do in fact refer to the same object. In this proposal we use a model of deduction for information flow that had been worked out for the introduction of threads into the C standard, namely the “carries a dependency” relation.

It ideally records any information flow that might go from one evaluation to another. We use this very general model for information dependency to cover all possible paths that might lead to pointer values that refer to the same object, but that originate in different sources relative to the block in question. The different forms of dependencies as listed above can all be used (or abused) to form a pointer to a given object, and the programmer who claims a restict has to guarantee that none of such constructed patterns leads to aliasing.

Another important feature of the new wording that we propose is that it attempts to properly distinguish lexical features from their execution time instantiation:

• Several instances of a block of a program can be active simultaneously (recursion, signal handlers, thread), so we have to distinguish a block B (the lexical feature) from a specific execution Bₓ (a runtime feature).

• Several instances of objects of automatic storage duration may exist at the same time (parameters qualified with restrict for example)

• Objects may have an effective type that is a restrict-qualified pointer type, without ever being declared as such.

• The only coherent notion of something similar to “time” is the “happens before” relation. It is used to describe when a store operation to an object (as a special case of an evaluation) takes place relative to another. In particular there is no consistent notion that a store operation happens before a block is executed, only a notion that it does not happen during the execution of a block.

3 An unresolved defect

The fact of using undefined behavior of the worrisome kind in its definition, is a major difficulty for tools to aid programmers in detecting erroneous usage of restrict. Nevertheless, this difficulty seems to be unavoidable, in view of the generality of the definition and in view of the essential run-time dependency.

There is one principal defect of the feature, though, that has been built into its design: the restric-feature lacks enforcement, even where that would be syntactically possible. This defect is due to the idea of modeling the feature with a qualifier that applies to a pointer type, but not to the pointer target. The analogy to the other two standard qualifiers const and volatile is really far fetched, and not really productive. These other qualifiers change the rules for access of the value under consideration, whereas restrict changes the rules of access of the target of the value under consideration.

In particular, here for restrict we have that qualifying a parameter is not part of a function type, and thus function declarations with different restrict-qualifications are compatible.

A restrict-qualification of a function parameter has no influence on the type of the function.

This has it that in general restrict-qualification remains fragile, needs thorough documentation and relies on voluntary cooperation between function provider and function caller.

In this paper here, we will not address this defect, but just try to provide a sound specification of the feature as it has been intended and understood.

4 Wording

Replace 6.7.4.2, title and p1–p5 by the following.

6.7.4.2 The semantics of the restrict qualifier

¹The intent is to provide optimization opportunities to the translator, such as reordering or dead-store elimination. In general, the verification of the requested properties lies in the responsibility of the programmer; either by ensuring that they hold for all possible executions of block B, or, by enforcing that B is never reached if the properties are not verified.

²In the following an index ₓ such as in Bₓ to the name of a lexical feature B of the program indicates a specific instance of that feature during an execution of the program currently under consideration.