Lightning talk #5 – Sequence points, ordering of evaluation, and undefined behavior

lightning-talks

Sequence point

sequence point defines any point in a computer program’s execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed. Adding more sequence points is sometimes necessary to make an expression defined and to ensure a single valid order of evaluation.

Places in which sequence points occur:

  1. Between evaluation of the left and right operands of the &&, ||, and comma operators.

First we validate the pointer, then the map, and only after that the size of the map.

  1. Between the first operand of “?” operator and the second / third operand.

There is a sequence point after b++, meaning that it has already been incremented by the time the right side is executed.

  1. At the end of a full expression. eg. expression statements ( a=b; ), return statements, language expressions (if, switch, while, do while) and all three expressions in the for statement.
  2. Before entering a function call. The order in which the arguments are evaluated is not specified, but all side effects of them are complete BEFORE the function body is entered.

  1. At a function return
  2. At the end of an initializer

Side Effects of Expression Evaluation

Before we delve into sequence points, let’s clarify what the side effects of expression evaluation are.  The side effects that a C++ program can produce are:

  • Modification of an object, that is, modification of some memory location or register.
  • Access to an object that is declared volatile.
  • Invocation of a system routine that produces side effects, like for instance input or output to files.
  • Invocation of functions that perform any of the above.

From the evaluation order proposal paper from H. Sutter:

Given an expression such as f(a, b, c), the order in which the sub-expressions f, a, b, c are evaluated is left unspecified by the standard. If any two of these sub-expressions happen to modify the same object without intervening sequence points, the behavior of the program is undefined.

For instance, the expression f(i++, i) where i is an integer variable leads to undefined behavior, as does v[i] = i++. Even when the behavior is not undefined, the result of evaluating an expression can still be anybody’s guest.

Consider the following program fragment:

What should the map object m look like after evaluation of the statement marked 

#1?   {{0, 0}} or {{0, 1}} ?

Ordering of evaluation

In C++11 the language changed and it no longer uses sequence points but ordering of evaluations: Sequenced before, unsequenced and Indeterminately sequenced.

  • Postfix expressions are evaluated from left to right. This includes functions calls and member section expressions.
  • Assignment expressions are evaluated from right to left. This includes compound assignments.
  • Operands to shift operators are evaluated from left to right.

In summary, the following expressions are evaluated in the order a, then b, then c, then d:

“sequenced-before” is an asymmetric, transitive, pair-wise relationship between evaluations within the same thread (it may extend across threads if atomic types and memory barriers are involved).

  • If a sequence point is present between the subexpressions E1 and E2, then both value computation and side effects of E1 are sequenced-before every value computation and side effect of E2
  • If evaluation A is sequenced before evaluation B, then evaluation of A will be complete before evaluation of B begins.
  • If A is not sequenced before B and B is sequenced before A, then evaluation of B will be complete before evaluation of A begins.
  • If A is not sequenced before B and B is not sequenced before A, then two possibilities exist:
    • evaluations of A and B are unsequenced: they may be performed in any order and may overlap (within a single thread of execution, the compiler may interleave the CPU instructions that comprise A and B)
    • evaluations of A and B are indeterminably-sequenced: they may be performed in any order but may not overlap: either A will be complete before B, or B will be complete before A. The order may be the opposite the next time the same expression is evaluated.

Undefined behavior

1) If a side effect on a scalar object is unsequenced relative to another side effect on the same scalar object, the behavior is undefined.

2) If a side effect on a scalar object is unsequenced relative to a value computation using the value of the same scalar object, the behavior is undefined.

3) The above rules apply as long as at least one allowable ordering of subexpressions permits such an unsequenced side-effect.

Leave a comment

Your email address will not be published.