Sequence Points and Partial Order

Sequence points and partial order

The C standard says this about assignment operators (C90 6.3.16 or C99 6.5.16 Assignment operators):

The side effect of updating the stored value of the left operand shall occur between the previous and the next sequence point.

It seems to me that in the statement:

i=(i,i++,i)+1;

the sequence point 'previous' to the assignment operator would be the second comma operator and the 'next' sequence point would be the end of the expression. So I'd say that the expression doesn't invoke undefined behavior.

However, this expression:

*(some_ptr + i) = (i,i++,i)+1;

would have undefined behavior because the order of evaluation of the 2 operands of the assignment operator is undefined, and in this case instead of the problem being when the assignment operator's side effect takes place, the problem is you don't know whether the value of i used in the left handle operand will be evaluated before or after the right hand side. This order of evaluation problem doesn't occur in the first example because in that expression the value of i isn't actually used in the left-hand side - all that the assignment operator is interested in is the "lvalue-ness" of i.

But I also think that all this is sketchy enough (and my understanding of the nuances involved are sketchy enough) that I wouldn't be surprised if someone can convince me otherwise (on either count).

sequence points in c

When a sequence point occurs, it basically means that you are guaranteed that all previous operations are complete.

Changing a variable twice without an intervening sequence point is one example of undefined behaviour.

For example, i = i++; is undefined because there's no sequence point between the two changes to i.

Note that it's not just changing a variable twice that can cause a problem. It's actually a change involved with any other use. The standard uses the term "value computation and side effect" when discussing how things are sequenced. For example, in the expression a = i + i++, the i (value computation) and i++ (side effect) may be done in arbitrary order.

Wikipedia has a list of the sequence points in the C and C++ standards although the definitive list should always be taken from the ISO standard. From C11 appendix C (paraphrased):

The following are the sequence points described in the standard:

Between the evaluations of the function designator and actual arguments in a function call and the actual call;
Between the evaluations of the first and second operands of the operators &&, ||, and ,;
Between the evaluations of the first operand of the conditional ?: operator and whichever of the second and third operands is evaluated;
The end of a full declarator;
Between the evaluation of a full expression and the next full expression to be evaluated. The following are full expressions:
- 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 expressions of a for statement;
- the expression in a return statement.
Immediately before a library function returns;
After the actions associated with each formatted input/output function conversion specifier;
Immediately before and immediately after each call to a comparison function, and also between any call to a comparison function and any movement of the objects passed as arguments to that call.

Undefined behavior and sequence points

C++98 and C++03

This answer is for the older versions of the C++ standard. The C++11 and C++14 versions of the standard do not formally contain 'sequence points'; operations are 'sequenced before' or 'unsequenced' or 'indeterminately sequenced' instead. The net effect is essentially the same, but the terminology is different.

Disclaimer : Okay. This answer is a bit long. So have patience while reading it. If you already know these things, reading them again won't make you crazy.

Pre-requisites : An elementary knowledge of C++ Standard

What are Sequence Points?

The Standard says

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. (§1.9/7)

Side effects? What are side effects?

Evaluation of an expression produces something and if in addition there is a change in the state of the execution environment it is said that the expression (its evaluation) has some side effect(s).

For example:

int x = y++; //where y is also an int

In addition to the initialization operation the value of y gets changed due to the side effect of ++ operator.

So far so good. Moving on to sequence points. An alternation definition of seq-points given by the comp.lang.c author Steve Summit:

Sequence point is a point in time at which the dust has settled and all side effects which have been seen so far are guaranteed to be complete.

What are the common sequence points listed in the C++ Standard?

Those are:

at the end of the evaluation of full expression (§1.9/16) (A full-expression is an expression that is not a subexpression of another expression.)¹
Example :
```
int a = 5; // ; is a sequence point here
```
in the evaluation of each of the following expressions after the evaluation of the first expression (§1.9/18) ²
- a && b (§5.14)
- a || b (§5.15)
- a ? b : c (§5.16)
- a , b (§5.18) (here a , b is a comma operator; in func(a,a++) , is not a comma operator, it's merely a separator between the arguments a and a++. Thus the behaviour is undefined in that case (if a is considered to be a primitive type))
at a function call (whether or not the function is inline), after the evaluation of all function arguments (if any) which
takes place before execution of any expressions or statements in the function body (§1.9/17).

_{1 : Note : the evaluation of a full-expression can include the evaluation of subexpressions that are not lexically
part of the full-expression. For example, subexpressions involved in evaluating default argument expressions (8.3.6) are considered to be created in the expression that calls the function, not the expression that defines the default argument}

_{2 : The operators indicated are the built-in operators, as described in clause 5. When one of these operators is overloaded (clause 13) in a valid context, thus designating a user-defined operator function, the expression designates a function invocation and the operands form an argument list, without an implied sequence point between them.}

What is Undefined Behaviour?

The Standard defines Undefined Behaviour in Section §1.3.12 as

behavior, such as might arise upon use of an erroneous program construct or erroneous data, for which this International Standard imposes no requirements ³.

Undefined behavior may also be expected when this
International Standard omits the description of any explicit definition of behavior.

_{3 : permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or with-
out the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).}

In short, undefined behaviour means anything can happen from daemons flying out of your nose to your girlfriend getting pregnant.

What is the relation between Undefined Behaviour and Sequence Points?

Before I get into that you must know the difference(s) between Undefined Behaviour, Unspecified Behaviour and Implementation Defined Behaviour.

You must also know that the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified.

For example:

int x = 5, y = 6;

int z = x++ + y++; //it is unspecified whether x++ or y++ will be evaluated first.

Another example here.

Now the Standard in §5/4 says

1. Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression.

What does it mean?

Informally it means that between two sequence points a variable must not be modified more than once.
In an expression statement, the next sequence point is usually at the terminating semicolon, and the previous sequence point is at the end of the previous statement. An expression may also contain intermediate sequence points.

From the above sentence the following expressions invoke Undefined Behaviour:

i++ * ++i;   // UB, i is modified more than once btw two SPs
i = ++i;     // UB, same as above
++i = 2;     // UB, same as above
i = ++i + 1; // UB, same as above
++++++i;     // UB, parsed as (++(++(++i)))

i = (i, ++i, ++i); // UB, there's no SP between `++i` (right most) and assignment to `i` (`i` is modified more than once btw two SPs)

But the following expressions are fine:

i = (i, ++i, 1) + 1; // well defined (AFAIK)
i = (++i, i++, i);   // well defined 
int j = i;
j = (++i, i++, j*i); // well defined

1. Furthermore, the prior value shall be accessed only to determine the value to be stored.

What does it mean? It means if an object is written to within a full expression, any and all accesses to it within the same expression must be directly involved in the computation of the value to be written.

For example in i = i + 1 all the access of i (in L.H.S and in R.H.S) are directly involved in computation of the value to be written. So it is fine.

This rule effectively constrains legal expressions to those in which the accesses demonstrably precede the modification.

Example 1:

std::printf("%d %d", i,++i); // invokes Undefined Behaviour because of Rule no 2

Example 2:

a[i] = i++ // or a[++i] = i or a[i++] = ++i etc

is disallowed because one of the accesses of i (the one in a[i]) has nothing to do with the value which ends up being stored in i (which happens over in i++), and so there's no good way to define--either for our understanding or the compiler's--whether the access should take place before or after the incremented value is stored. So the behaviour is undefined.

Example 3 :

int x = i + i++ ;// Similar to above

Follow up answer for C++11 here.

Is one side of an assignment sequenced before the other in c++?

a[i] = foo();

Here it is unspecified whether foo or a[i] is evaluted first. In the new C++11 wording, the two evaluations are unsequenced. That alone doesn't cause undefined behaviour, though. It is when there are two unsequenced accesses to the same scalar object, at least one of which is writing, where it does. That's why a[i] = i++; is UB.

The difference between these two statements is that a call to foo() does introduce a sequence point. C++11 wording is different: executions inside a called function are indeterminately sequenced with respect to other evaluations inside the calling function.

This means there's a partial ordering between a[i] and i++ inside foo. As a result, either a[0] or a[1] will get set to 0, but the program is well defined.

Relationship between C11 atomics and sequence points

To answer the question in your title, there is no real relationship between atomics and sequence points.

The code as written does guarantee that the compiler must execute the atomic_fetch_sub before the atomic_load. But these functions are (in C's memory model) simply requests to the platform to perform certain actions on certain pieces of memory. Their effects, when they become visible to who, are specified by the memory model, and the ordering parameters. Thus even in the case when you know request A comes before request B, that does not mean the effects of request A are resolved before request B, unless you explicitly specify it to be.

Sequence points in simple words

Expressions such as n++ have side effects, i.e. they not only produce a result, but also modify a variable.

The * operator does not introduce a sequence point. Therefore, in the expression n++ * n-- it is not specified, whether the side effect of n++ (incrementing n) has already happened when n-- is evaluated. Depending on that, n++ * n-- yields different results.

; introduces a sequence point. If n == 5, then after n++; n--;, n == 5 holds again.

New Sequence Points in C++11

The UB in those cases is based on [intro.execution]/15

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced. [...] The value computations of the operands of an operator are sequenced before the value computation of the result of the operator. If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined.

For ++(++i): [expr.pre.incr]/1 states that ++i is defined as i+=1. This leads to [expr.ass]/1, which says

In all cases, the assignment is sequenced after the value computation of the right and left operands, and before the value computation of the assignment expression.

Therefore, for ++(++i), equivalent to (i+=1)+=1, the inner assignment is sequenced before the outer assignment, and we have no UB.

[intro.execution]/15 has an example of UB:

i = i++ + 1; // the behavior is undefined

The case here is a bit different (thanks to Oktalist for pointing out a pre/postfix mistake here). [expr.post.incr]/1 describes the effects of postfix increment. It states:

The value computation of the ++ expression is sequenced before the modification of the operand object.

However, there is no requirement on the sequencing of the side effect (the modification of i). Such a requirement could also be imposed by the assignment-expression. But the assignment-expression only requires the value computations (but not the side effects) of the operands to be sequenced before the assignment. Therefore, the two modifications via i = .. and i++ are unsequenced, and we get undefined behaviour.

N.B. i = (i = 1); does not have the same problem: The inner assignment guarantees the side effect of i = 1 is sequenced before the value computation of the same expression. And the value is required for the outer assignment, which guarantees that it (the value computation of the right operand (i = 1)) is sequenced before the side effect of the outer assignment. Similarly, i = ++i + 1; (equivalent to i = (i+=1) + 1;) has defined behaviour.

The comma operator is an example where the side effects are sequenced; [expr.comma]/1

Every value computation and side effect associated with the left expression is sequenced before every value computation and side effect associated with the right expression.

[intro.execution]/15 includes the example i = 7, i++, i++; (read: (i=7), i++, i++;), which is defined behaviour (i becomes 9).

Sequence points when calling functions in C and undefined/unspecified behaviour

No, per 6.5.2.2 10 there is no sequence point between the evaluation of subexpression arguments, just before the actual call.

One way of looking at it is that it is unspecified whether the behaviour is undefined; if the implementation sequences the two ++i subexpressions before any call to g or h then the behaviour is undefined, but if the ++i subexpressions are evaluated as late as possible (immediately before calling g and h respectively) then the behaviour is unspecified. However, because the implementation is always at liberty to choose between any allowed unspecified behaviour then the overall result is undefined.

Assignment operator and side effects with sequence points

C99 5.1.2.3 defines sequence points as the places by which all side effects of the previous evaluations have taken place and the side effect of subsequent evaluations have not yet started taking place. The annex C of the standard defines the places where the sequence points take place: function calls, end of logical operators, the comma operator, and the ternary operator, end of a full declarations, end of a full expression, and so on.

In this case, the previous sequence point is the start of main(), and the next sequence point is the semicolon at the end of the assignment. At the first sequence point, x will have a value of 42, and at the second one, it will be 0.

Sequence Points and Partial Order