A finer-grained specification of sequencing

Probably few people in the world understand the problems in the current description of the sequencing rules of C, mainly using the term "sequence point", better than the members of WG14, who have already spent considerable time trying to find better terms of reference, without success. The earlier failures are certainly evidence that the problem is hard. So what might make it worthwhile to try again?

In a nutshell, the answer is parallel programming. In order to understand or specify the semantics of a program with multiple threads, it is absolutely essential to be able to understand and specify the semantics of a the threads that comprise it. Furthermore, if sequencing constraints within a thread are described indirectly, through sequence points, then the descriptions of interactions between threads also need to be described indirectly, probably resulting in something of a combinatorial explosion in the description. But if sequencing constraints on program operations are expressed directly, the descriptions of interactions between threads can be simpler. For example, the memory model for Java is described in terms of program actions such as loads and stores, without resorting to intermediate artifacts such as sequence points.

This paper outlines my thoughts about the problems with sequence points, and how they might be solved — in fact, how they will be solved in the next revision of C++. The purpose is not to make any technical changes, but to achieve a better description (and understanding) of the status quo. This is of course based on my own understanding of the status quo. If anyone thinks I am proposing unacceptable technical changes, that would be a reflection on the lack of clarity and/or specificity of the existing words.

Caveat: This proposal does explicitly ignore the impact sequence points currently have on what in C++ is called "lifetime of temporaries". (This issue was introduced to C99 as part of "conversion of array to pointer not limited to lvalues".) At least at the moment, that's just for my convenience, because wording to preserve the status quo would be considerably more complicated than what I have already formulated for C++, in which the lifetime of a temporary ends at the end of the full expression. N1253 explores this issue in more depth, and suggests that C switch to the C++ rule. If that suggestion is rejected, I will of course do the additional work to draft wording to preserve the status quo.

5.1.2.3p2: The definition of "sequence point"

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (A summary of the sequence points is given in annex C.)

When reading this statement, two qualifications must be kept in mind:

• Not every side effect or evaluation can be authoritatively determined to be either previous to or subsequent to a given sequence point. For example, given

  a = 0;
  b = (a = 1, 2*a) + 3*a;

  The evaluation of 3*a is not ordered with respect to the sequence point introduced by the comma operator. It may be previous or subsequent; the standard simply doesn't say. Therefore, that evaluation may or may not be separated from the assignment by a sequence point.

  The published C++ standard contains a sentence which considerably clarifies the intent. From C++ 5p4, which corresponds to C 6.5p2 (the "undefined behavior" rule):

  The requirements of this paragraph shall be met for each allowable ordering of the subexpressions of a full expression; otherwise the behavior is undefined.

  However, the C standard lacks any similar statement, so the intended interpretation can not be inferred strictly from the standard. But it is crucially important to have clear and unambiguous rules by which we can determine whether a given example is well-defined or undefined. (It should be noted that this specific sentence no longer appears in the WD for C++; my proposal made it redundant, and it was deleted.)

  In any event, because of the partially-ordering nature of sequence points, any reference to the operations falling between the previous and next sequence point is ambiguous — it's not always possible to tell what is and is not included in that set. In fact, because sequence points are themselves only partially ordered, any reference at all to "the" previous or next sequence point is potentially ambiguous. Unfortunately, the standard contains several such references.

• The statement is talking about the abstract machine, and is therefore subject to the as-if rule. For example, given

  int a = 0, b = 0;
  a = 1;
  b = 2;

  There need not be any point in the execution of the "concrete" machine at which a can be observed to be 1 and b can be observed to be 0, because in this example a and b are not both volatile. In other words, a state corresponding to the sequence point need not actually occur within the "concrete" machine.

For these reasons, I do not think of a sequence point as an event (in the concrete machine). Events in the concrete machine are such things as loads (evaluations) and stores (side effects) — transactions which are observable on some machine bus. A sequence point is certainly not an event in that sense.

I think that some (possibly much) of the confusion about sequence points is caused by thinking of them as events. Considering the example under the first bullet above, if the sequence point is considered to be a concrete event, then it must occur either before or after (or possibly concurrent with) other events in the concrete machine, and therefore may wind up between two events which the user wants to be separated by a sequence point, thereby preventing undefined behavior. The logic seems valid, but the conclusion is not, because the first example above is really supposed to have undefined behavior. So there must be a problem with a premise. QED

Instead, I think sequence points are nothing more than an editorial mechanism for expressing sequencing constraints on events. And I think that those constraints could be expressed more precisely and more clearly without that specific editorial mechanism, instead simply expressing them directly, using the term "sequenced before" as the name of the desired constraint. Here is my proposed rewrite. Text from the current standard to be replaced or deleted is stricken through. Replacement or added text is underlined.

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. Evaluation of an expression in general includes both value computations and initiation of side effects. Value computation for an lvalue expression includes determining the identity of the designated object.

"Sequenced before" is an asymmetric, transitive, pair-wise relation between evaluations executed by a single thread, which induces a partial order among those evaluations. Given any two evaluations A and B, if A is sequenced before B, then the execution of A shall precede the execution of B. If A is not sequenced before B, and B is not sequenced before A, then A and B are unsequenced. Evaluations A and B are indeterminately sequenced when either A is sequenced before B, or B is sequenced before A, but it is unspecified which.^Footnote The presence of a sequence point between the evaluation of expressions A and B implies that every value computation and side effect associated with A is sequenced before every value computation and side effect associated with B. (A summary of the sequence points is given in annex C.)

Footnote: The executions of unsequenced evaluations can interleave. Indeterminately sequenced evaluations can not interleave, but either could be executed first.

My purpose is to retain the term "sequence point" as a means of specifying most sequencing constraints, so for example descriptions of operators don't change materially, but to describe most consequences of the sequencing rules in terms of "sequenced before". However, note that a sequence point separates the evaluations of specific expressions; taking this into account will require tweaking some words.

Note that I have added a definition of "evaluation", and also the term "value computation" (not specifically defined) to refer to actions taken in expression evaluation that do not cause a side effect. The concept of "value computation" will be critical in my reformulation of the "undefined behavior" rule.

5.1.2.3p4: Asynchronous signals

When the processing of the abstract machine is interrupted by receipt of a signal, only the values of objects as of the previous sequence point may be relied on. Objects that may be modified between the previous sequence point and the next sequence point need not have received their correct values yet.

There are two kinds of signal: synchronous (as initiated by a call to raise or abort) and asynchronous.

For the synchronous case, it's not clear that there is or should be any significant difference between a signal handler that's activated by a call to a library function and one that's activated by a call to the handler itself. In other words, when a call is made, does it really matter whether signal handling is or might be involved in the activation of the (ultimately) invoked code? If not, this statement is true, but redundant, in that it could be deduced from the rules for function calls.

For the asynchronous case, I think it's clear that this statement is either false or misleading. According to 7.14.1.1p5, a signal handler can't even access any object (except to assign to a volatile sig_atomic_t object), much less rely on its value, regardless at what point the value may have been assigned. And if this statement were to be taken at face value, it would drastically limit optimization opportunities.

On the other hand, consider the corresponding statement from the published C++ standard (1.9p9):

When the processing of the abstract machine is interrupted by receipt of a signal, the values of objects with type other than volatile std::sig_atomic_t are unspecified, and the value of any object not of volatile std::sig_atomic_t that is modified by the handler becomes undefined.

I believe this statement says pretty much what should be said, in terms of what can safely be done in programs, and has pretty much the desired impact (i.e. little or none) on the validity of optimization with respect to handling asynchronous signals. Technically, there is a conflict with 7.14.1.1p5 , in the implication that an asynchronous signal handler may use the value of a volatile sig_atomic_t object, and not just assign to it. Perhaps this too should be considered well-defined, and the standard should say so explicitly.

In my view, this would not constitute a change from the status quo; it would effectively be a clarification of the status quo.

5.1.2.3p5: The "least requirements"

The least requirements on a conforming implementation are:

• At sequence points, volatile objects are stable in the sense that previous accesses are complete and subsequent accesses have not yet occurred.

The sense of this constraint is simply that, in the "concrete" machine, the sequence of accesses to volatile objects is constrained exactly as in the abstract machine. It should be possible to say so in basically those words, without reference to sequence points. Consider these words from the description of volatile (6.7.3p6):

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. ...

I propose this replacement:

The least requirements on a conforming implementation are:

• At sequence points, volatile objects are stable in the sense that previous accesses are complete and subsequent accesses have not yet occurred. Accesses to volatile objects are evaluated strictly according to the rules of the abstract machine.

6.5p2: Undefined behavior

Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be read only to determine the value to be stored. ^Footnote

Footnote: This paragraph renders undefined statements such as

i = ++i + 1;
a[i++] = i;

while allowing

i = i + 1;
a[i] = i;

Again, because sequence points are only partially ordered, the references to "the" previous and next sequence points are ambiguous at best. Also remember that problems have been discovered with the formulation "the prior value shall be accessed only to determine the value to be stored." The strictest interpretation of those words would outlaw any use of the value of a post-increment expression, since the prior value is also used to determine the value of the expression. There is also a problem with (a[a[0]] = x), where the prior value of a[0] is zero. In that case, the prior value is used to determine the identity of the object to be assigned, which the existing words do not allow. I suggest that this statement would be better expressed along the following lines:

Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be read only to determine the value to be stored. If a side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object, or a value computation using the value of the same scalar object, the behavior is undefined. The value computations of the operands of an operator are sequenced before the value computation of the result of the operator.

The second sentence provides a pragmatic definition of what is often called "dependence" or "causality". For the example {i = i + 1;}, by insisting that the load of i is sequenced before the value computation of (i + 1), and ultimately before the assignment to i, we specify that the example is well-defined, because the load and store of i are not relatively unsequenced.

It is also worth noting that this rule, and the associated "unspecified order" rule, are widely separated from the description of program execution in 5.1.2.3. This is not unreasonable given only single-threaded execution, but once threading is added to the standard, it would seem reasonable to take 5.1.2.3 as a description of the execution of a single thread, and add a new section to describe the execution of a multi-threaded program. Naturally, that section will have to say something about what happens in the presence of an inter-thread data race (probably undefined behavior). These rules effectively describes a data race that can happen within a single thread; it would probably make the standard easier to understand on a sequential reading if they were moved to 5.1.2.3.

6.5p3: Unspecified order

The grouping of operators and operands is indicated by the syntax. Except as specified later (for the function-call (), &&, ||, ?:, and comma operators), the order of evaluation of subexpressions and the order in which side effects take place are both unspecified.

There's no actual problem, but what is here described as taking place in unspecified order must, in my terminology, be described as being unsequenced. Furthermore, the sequencing operators are not the only constraints on sequencing: there is also, for example, the end of a full expression.

The grouping of operators and operands is indicated by the syntax. Except as specified later (for the function-call (), &&, ||, ?:, and comma operators), the order of evaluation , side effects and value computations of subexpressions and the order in which side effects take place are both unspecified unsequenced ^Footnote.

Footnote: In an expression that is evaluated more than once during the execution of a program, unsequenced and indeterminately sequenced evaluations of its subexpressions need not be performed consistently in different evaluations.

The proposed footnote points out a non-requirement that is believed to be implicit in the status quo. It is desirable for optimizations such as loop unrolling and inlining, where code is effectively duplicated. It should be enough for an implementation to ensure that the semantics required by the standard are satisfied by each duplicated instance; it should not be necessary to maintain consistency in aspects where the standard doesn't impose requirements.

6.5.2.2p10: Function calls

The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified, but there is a sequence point before the actual call.

The statement of unspecified order here is redundant with 6.5p3. Also, the statement about the position of the sequence point needs to be updated to specify the exact expressions so separated. Furthermore, we have an opportunity, as well as the means (and hopefully motive as well), to state normatively that executions of different function invocations do not interleave.

The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified, but there There is a sequence point after the evaluations of the function designator and actual arguments, and before the actual call. Every evaluation in the calling function (including other function calls) that is not otherwise specifically sequenced before or after the execution of the body of the called function is indeterminately sequenced with respect to the execution of the called function. ^Footnote

Footnote: In other words, function executions do not "interleave" with each other.

6.5.2.4p2: Postfix increment and decrement operators

The result of the postfix ++ operator is the value of the operand. After the result is obtained, the value of the operand is incremented. (That is, the value 1 of the appropriate type is added to it.) See the discussions of additive operators and compound assignment for information on constraints, types, and conversions and the effects of operations on pointers. The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point.

Note that there is here a necessary sequencing constraint, which is already specified in terms more fine than that of a sequence point: the modification must follow the evaluation.

Also, consider this troublesome example, which the committee considered in Portland:

int increment_x() { x++; }
x++ + increment_x();                // Evaluation order unspecified; x may be incremented only once
increment_x() + increment_x();      // x is incremented twice

The point of this example is that, in the second line, the call to increment_x might occur between the load of x and the store of its incremented value. Everything that is presented here about post-increment (or post-decrement) is also true of compound assignment.

Firstly, it is not clear from the existing standard whether the interpretation that allows the outcome described in the example is correct or not; therefore, the status quo is a matter of opinion, with different experts expressing different opinions.

Secondly, it is clear that the existing standard describes the example as having unspecified behavior, but not undefined behavior. The standard is clear (in 4p3) that unspecified behavior, of itself, is allowed in a "correct" program. If the example expression is truly as unreliable as is claimed, it really should be categorized as having undefined behavior.

But between the alternatives of reclassifying the expression as having undefined behavior, and of tightening the sequencing rules sufficiently to eliminate the possibility of (apparently) losing a side effect, the latter is far less radical, easier to specify, more conducive to writing reliable programs, and probably has minimal if any impact on existing implementations.

The formulation I would propose for the sequencing constraints goes something like this:

The result of the postfix ++ operator is the value of the operand. After the result is obtained, the The value of the operand object is incremented. (That is, the value 1 of the appropriate type is added to it.) See the discussions of additive operators and compound assignment for information on constraints, types, and conversions and the effects of operations on pointers. The value computation of the result is sequenced before the side effect of updating the stored value of the operand shall occur between the previous and the next sequence point. With respect to an indeterminately-sequenced function call, the operation of postfix ++ is a single evaluation.

6.5.13p4: Logical AND operator

Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; there is a sequence point after the evaluation of the first operand. If the first operand compares equal to 0, the second operand is not evaluated.

The only change needed here would be to properly "scope" the sequence point:

Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; if the second operand is evaluated, there is a sequence point after between the evaluation evaluations of the first and second operands operand. If the first operand compares equal to 0, the second operand is not evaluated.

Obviously, the changes for logical OR would be exactly analogous.

6.5.15p4: Conditional operator

The first operand is evaluated; there is a sequence point after its evaluation. The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand (whichever is evaluated), converted to the type described below. If an attempt is made to modify the result of a conditional operator or to access it after the next sequence point, the behavior is undefined.

The problem and solution here are very similar to the logical-and expression immediately above:

The first operand is evaluated; there is a sequence point after between its evaluation and the evaluation of the second or third operand (whichever is evaluated). The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand (whichever is evaluated), converted to the type described below. If an attempt is made to modify the result of a conditional operator or to access it after the next sequence point, the behavior is undefined.

(The only reason I am not proposing to change the last sentence of this paragraph is that it is related to the "lifetime of temporaries" issue.)

6.5.16p3-4: Assignment operators

An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment, but is not an lvalue. The type of an assignment expression is the type of the left operand unless the left operand has qualified type, in which case it is the unqualified version of the type of the left operand. The side effect of updating the stored value of the left operand shall occur between the previous and the next sequence point.

The order of evaluation of the operands is unspecified. If an attempt is made to modify the result of an assignment operator or to access it after the next sequence point, the behavior is undefined.

The phrase "shall occur between the previous and next sequence point", which also appears in the description of post-increment above, is really redundant; it is implied by the words describing the construct that introduces the sequence point. If there is any value in saying that here, it is to emphasize the fact that the sequencing of the side effect is fairly loose — which is also redundant.

On the other hand, the words above which describe causality constrain only value computations. To be complete, they should also constrain side effects. And finally, here again "unspecified order" needs to be "unsequenced".

An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment, but is not an lvalue. The type of an assignment expression is the type of the left operand unless the left operand has qualified type, in which case it is the unqualified version of the type of the left operand. The side effect of updating the stored value of the left operand shall occur between the previous and the next sequence point is sequenced after the value computations of the left and right operands.

The order of evaluation evaluations of the operands is unspecified are unsequenced. If an attempt is made to modify the result of an assignment operator or to access it after the next sequence point, the behavior is undefined.

It is extremely important to note here that the assignment is not sequenced after any side effects of the operands, but only after their value computations. That is why the definition of a sequence point refers separately to evaluations and side effects; so that it is also possible to express weaker sequencing constraints. I used the same trick above in my proposal for post-increment.

6.5.16.2p3: Compound assignment

A compound assignment of the form E1 op= E2 differs from the simple assignment expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once.

As with post-increment, I believe compound assignment should be atomic — at least within the context of a single thread of execution.

A compound assignment of the form E1 op= E2 differs from is equivalent to the simple assignment expression E1 = E1 op (E2) only in , except that the lvalue E1 is evaluated only once , and with respect to an indeterminately-sequenced function call, the operation of a compound assignment is a single evaluation.

6.5.17p2: Comma operator

The left operand of a comma operator is evaluated as a void expression; there is a sequence point after its evaluation. Then the right operand is evaluated; the result has its type and value. If an attempt is made to modify the result of a comma operator or to access it after the next sequence point, the behavior is undefined.

As with other sequencing operators, it is necessary to specify exactly which subexpressions are affected by the constraints of the sequence point.

The left operand of a comma operator is evaluated as a void expression; there is a sequence point after between its evaluation and that of the right operand. Then the right operand is evaluated; the result has its type and value. If an attempt is made to modify the result of a comma operator or to access it after the next sequence point, the behavior is undefined.

6.8p4: Full expressions

A full expression is an expression that is not part of another expression or of a declarator. Each of the following is a full expression: an initializer; the expression in an expression statement; the controlling expression of a selection statement (if or switch); the controlling expression of a while or do statement; each of the (optional) expressions of a for statement; the (optional) expression in a return statement. The end of a full expression is a sequence point.

Again, we want to say what expressions are separated by the sequence point:

A full expression is an expression that is not part of another expression or of a declarator. Each of the following is a full expression: an initializer; the expression in an expression statement; the controlling expression of a selection statement (if or switch); the controlling expression of a while or do statement; each of the (optional) expressions of a for statement; the (optional) expression in a return statement. The end of a full expression is a sequence point. There is a sequence point between the evaluation of a full expression and the evaluation of the next full expression to be evaluated.

It may seem to be hand-waving to refer to "the next full expression to be evaluated", when what we are mainly trying to do is to nail down sequencing requirements (i.e. what is required/allowed to be "next"). But the ambiguities with sequence points have to do with sequencing operators within a full expression; there's really no question what a sequence point between full expressions means. So the specification of the sequence of evaluations of full expressions is effectively a "higher-level protocol", and is (already) specified elsewhere.