Sequence Points and C11 Sequenced-Before Explained

This article provides an overview of how the C language governs the order of operations and side effects during execution. It covers the traditional concept of sequence points used in C89 and C99, explains why this model was flawed, and details how the C11 standard introduced the "sequenced-before" relationship to provide a rigorous, partial-order model that accommodates both single-threaded execution and modern multithreading.

The Concept of Sequence Points (C89 / C99)

In earlier revisions of the C standard (C89 and C99), program execution was framed around sequence points. A sequence point was defined as a designated point in the execution sequence at which all side effects of previous evaluations are guaranteed to be complete, and no side effects of subsequent evaluations have yet taken place.

Between two consecutive sequence points, the order of evaluation of subexpressions and the order in which side effects occur are unspecified. Consequently, the standards imposed a strict rule:

Between the previous and next sequence point, an object's stored value could be modified at most once by the evaluation of an expression. Furthermore, the prior value could be accessed only to determine the value to be stored.

Violating this rule resulted in undefined behavior (UB). For instance:

i = i++;       // Undefined behavior: modified more than once
a[i] = i++;    // Undefined behavior: modified and read not to determine value
f(i++, i++);   // Undefined behavior: modified multiple times without a sequence point

Common sequence points included:

  • The end of a full expression (typically at a semicolon).
  • The &&, ||, and comma (,) operators, which introduce a sequence point after evaluation of the first operand.
  • The ? : conditional operator, after evaluation of the first operand.
  • A function call, after all function arguments are evaluated and before any code inside the function is executed.

Limitations of the Sequence Point Model

While intuitive, sequence points suffered from significant conceptual limitations:

  1. Lack of Mathematical Rigor: Sequence points treated execution as a flat timeline punctuated by barriers. They struggled to formalize expressions where evaluations do not take place simultaneously but are still arbitrarily ordered.
  2. Poor Fit for Multithreading: Sequence points were strictly a single-threaded abstraction. They could not be integrated cleanly into modern memory models requiring formal memory-order semantics (such as acquire/release operations and atomic data types).
  3. Interleaving Ambiguities: The model could not precisely distinguish between operations that can occur in any order vs. operations whose internal instructions can actively interleave.

The C11 Refinement: The Sequenced-Before Model

To resolve these ambiguities and align with the C++11 memory model, the C11 standard replaced sequence points with asymmetric, transitive evaluation orderings defined as the sequenced-before relationship.

In C11, an expression evaluation consists of both value computations (determining the result of an operator or operand) and side effects (modifying execution environment state, such as writing to an object or calling an I/O routine).

Instead of relying on global checkpoints, C11 defines the relative ordering of any two evaluations \(A\) and \(B\) performed by the same thread using four relation states:

  1. Sequenced Before: \(A\) is sequenced before \(B\) if the evaluation of \(A\) completes before the evaluation of \(B\) begins.
  2. Sequenced After: \(B\) is sequenced before \(A\).
  3. Indeterminately Sequenced: \(A\) is sequenced before \(B\), or \(B\) is sequenced before \(A\), but the choice is unspecified. Crucially, their evaluations cannot overlap or interleave.
  4. Unsequenced: Neither \(A\) is sequenced before \(B\) nor \(B\) is sequenced before \(A\). The compiler may execute their sub-operations in any order, including interleaving their constituent instructions.

Undefined Behavior in C11

The C11 standard redefined the criteria for evaluation-based undefined behavior in ยง6.5p2:

If a side effect on a scalar object is unsequenced relative to either:

  1. another side effect on the same scalar object, or
  2. a value computation using the value of the same scalar object,

the behavior is undefined.

Consider the expression (i++) + i:

  • The value computation of the left operand involves a side effect: updating i.
  • The right operand computes the value of i.
  • The standard does not specify an evaluation order between the left and right operands of the binary + operator; they are unsequenced.
  • Because a side effect on i is unsequenced relative to a value computation of i, the expression produces undefined behavior.

How C11 Formalizes Common Constructs

C11 cleanly classifies situations that were previously lumped together under sequence points:

  • Function Arguments: In a function call f(a(), b()), the evaluation of a() and b() are indeterminately sequenced. One will finish entirely before the other begins, preventing instruction interleaving, but the order in which they run is unspecified.
  • Short-Circuit Operators: In expr1 && expr2, the value computation and side effects of expr1 are explicitly sequenced before those of expr2.
  • Assignment: The side effect of updating the target storage is sequenced after the value computations of both the left and right operands.

By transitioning from sequence points to the sequenced-before relation, C11 created a mathematically sound foundation for single-threaded evaluations that connects directly into the broader "happens-before" multithreading model defined in <stdatomic.h>.