1. Introduction
C and C++ diverge in their definition of forward progress guarantees, and have done so since C++11 and C11 added a memory model and acknowledged that threads exist. Both committees have been working together to reduce needless differences. [P2735r0] and [N2644] perform such harmonization.
C does not make iteration statements whose controlling expression is a constant expression Undefined Behavior, whereas C++ does. C++ implementations therefore assume that even "trivial" infinite loops must terminate.
This is unfortunate because using an infinite loop is a common idiom in low-level programming, particularly when a bare-metal system or kernel must halt progress. It would be easy for programmers to satisfy the C++ requirements on infinite loops, and it would be easy for compilers to diagnose "invalid" infinite loops. Neither programmers nor implementations have done so. Instead, programmers decry C++'s obtuseness, and implementations upset developers by optimizing away their infinite loops (marking them as unreachable, leading to surrounding code being optimized away).
For example, this code prints
in recent versions of clang (see example):
#include <iostream>int main () { while ( true) ; } void unreachable () { std :: cout << "Hello world!" << std :: endl ; }
It is easy for the C++ Standards Committee to instead align with C, and allow "trivial" infinite loops as C does. However, care must be taken when doing so. C++ has good reasons to specify that infinite loops are undefined behavior: it is desirable to express forward progress guarantees in a programming language because it unlocks a design space in concurrency and parallelism software and hardware design. An 80 minute deep-dive in this topic is available in [ForwardProgress]. A definition of "trivial" which continues supporting this design space is important to reach.
Other programming languages, compilers, and hardware explicitly or de-facto rely on the C++ specification of its abstract machine, including the behavior infinite loops. Some by borrowing from C++'s specification, others by simply using compilers that implement C++ as their optimizer (see [LLVMProgressDiscussion], and a Rust bug of this shape), and yet others by being designed around C++ programs. It is therefore likely that a broader specification for an abstract machine, outside of C++, is needed to truly resolve problems as those tackled in this paper.
2. Revision History
[P2809r0] proposed matching the C semantics. It was discussed at the 2023 Varna meeting and received feedback from SG1 against matching C semantics, as explained below.
3. Standards
Since C++11, the Standard’s forward progress guarantees have been defined in [intro.progress] as follows:
The implementation may assume that any thread will eventually do one of the following:
terminate,
make a call to a library I/O function,
perform an access through a
glvalue, or
volatile perform a synchronization operation or an atomic operation.
[Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. —end note]
This forward progress guarantee applies to the following iteration statements:
while condition
( statement
)
statement
do
while expression
(
)
;
for init-statement conditionopt
( expressionopt
; statement
)
for init-statementopt for-range-declaration
( for-range-initializer
: statement
)
Since C11, the Standard’s forward progress guarantees have been defined in Iteration statements (section 6.8.5 of C17) as follows:
An iteration statement may be assumed by the implementation to terminate if its controlling expression is not a constant expression†, and none of the following operations are performed in its body, controlling expression or (in the case of astatement) its expression-3‡:
for
input/output operations
accessing a
object
volatile synchronization or atomic operations.
† An omitted controlling expression is replaced by a nonzero constant, which is a constant expression.
‡ This is intended to allow compiler transformations such as removal of empty loops even when termination cannot be proven.
This forward progress guarantee applies to the following iteration statements:
while expression
( statement
)
statement
do
while expression
(
)
;
for expressionopt
( expressionopt
; expressionopt
; statement
)
for declaration expressionopt
( expressionopt
; statement
)
By omission, iteration statements are undefined if the controlling expression does not meet the criteria above.
4. History
C99 6.8.5p4 states:
An iteration statement causes a statement called the loop body to be executed repeatedly until the controlling expression compares equal to 0
.
C99 therefore disallows compilers from assuming that loops will eventually terminate.
C++11 added a full memory model to C++, allowing C++ to speak of threads and inter-thread communications in a useful manner. This forward progress guarantee does away with the C99 guarantee above. A key to concurrency and parallelism is understanding when forward progress is guaranteed, because without forward progress some concurrent and parallel algorithms do not work. For example, a pair of producer / consumer threads will never consume data if the producer does not have forward progress.
This memory model work was imported into the C11 standard through [N1349]. There were discussions on the topic of forward progress:
-
[N1509] proposed eliminating the paragraph on forward progress from C1X.
-
[N1528] responded to N1509, explaining the C1X wording.
These two papers were discussed, and WG14 took the following decision:
ACTION Douglas to work with Larry to come up with the proposed words are:Change 6.8.5p6 as follows:
An iteration statement whose controlling expression is not a constant expression (or omitted), that performs no input/output operations, does not accessobjects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a
volatile statement) its expressionX3, may be assumed by the implementation to terminate.
for Decision: Adopt N1509, as modified above, to the C1X WP. result: 14 favor, 0 neutral, 1 against
5. Rationale
The forward progress guarantees were added to C++11 and C11 along with a memory model. This addition of forward progress guarantees reflected existing practice in compilers, and did not simply serve concurrency and parallelism goals. Indeed, compilers had been assuming that loops can terminate to enable optimizations that transform loops and reorder store instructions and other side-effects. Proving that loops terminate is generally equivalent to solving the halting problem. The compilers were therefore disregarding the C99 wording which said that loops terminate when their controlling expression becomes
, and were therefore non-conformant.
The standards added the forward progress guarantees to change an optimization problem from "solve the halting problem" to "there will be observable side effects in the forms of termination, I/O,
, and/or atomic synchronization, any other operation can be reordered". The former is generally impossible to solve, whereas the latter is eminently tractable.
Forward progress guarantees therefore helped program concurrency and parallelism, and standardized existing practice which unlocked performance in compiler optimizations.
However, developers do sometimes rely on infinite loops, for valid reasons. When they do so, the loops have controlling expressions which are constant expressions. Such controlling expressions are known at compile-time by definition, and are therefore easy for a compiler to detect, and mark a loop as not open to optimizations which assume termination.
That said, an issue arises with the current wording in C, because this loop:
while ( cond ) { // ... }
is not equivalent to that loop:
while ( true) { if ( ! cond ) break ; // ... }
Because its controlling expression is not a constant expression. This difference is surprising because the loops look syntactically equivalent. The same applies for any loop which has a constant expression controlling expression that converts to true
, and has a
,
, or (potentially nested)
.
We could conside a change such as adding an implicit
to all loops whose controlling expression is a constant expression, but doing so would needlessly pessimize code. This pessimization would likely be measured in multiples for GPU code. Indeed, without the
some GPU hardware would halt forward progress on all warps in a thread block if one of the warps were to have an infinite loop. This behavior is acceptable while infinite loops are Undefined Behavior, but pessimizes loops which aren’t infinite (and therefore don’t exhibit forward progress issues).
The approach with
also causes problems pertaining to code motion: a compiler is no longer allowed to hoist code from below a loops whose controlling expression is a constant expression to above it, nor merge loops whose whose controlling expression is a constant expression. This is also a pessimization which affects more than "trivial" infinite loops.
A change is therefore required which does not match the C semantics, and C would then need to be updated to match. It should be pointed out that C technically does not have forward progress guarantees, but hints at maybe having some guarantees, thefore changes to C ought to consider also adding forward progress guarantees.
The proposed wording captures very narrowly a few forms of infinite loops and makes them equivalent to a call to a new function,
, which is freestanding. By doing so, the proposal does not pessimize certain types of loops as C does, and continues to allow an implementation to assume that most loops will terminate.
The proposed wording also adds to the list of allowed assumptions that a
function or
will be called. They were a missing form of valid non-forward-progress in threads that was discovered while discussing this paper in SG1.
This paper does not affect other forms of backwards control flow such as
,
/
, infinite tail recursion, nor looping with signal handlers. While they are also forms of loops, infinite versions of them are not idiomatic in C and C++. Functional programmers might be upset at this fact.
6. Library Wording
Modify [utility.syn] as follows:
The headercontains some basic function and class templates that are used throughout the rest of the library.
< utility >
namespace std { // ... // [utility.unreachable], unreachable [[ noreturn ]] void unreachable (); // [utility.halt], halt namespace this_thread { [[ noreturn ]] void halt () noexcept ; } // ... }
Also modify [thread.syn] as above.
Add a new section [utility.halt] as follows:
22.2.� Function halt [utility.halt]Effects: Equivalent to:
namespace this_thread { [[ noreturn ]] void halt () noexcept ; }
while true ( ) std :: this_thread :: yield ();
6.1. Library Bikeshed
could be named something else. Here are suggestions:
-
std :: infinite_loop -
std :: block_forever -
std :: sleep_forever -
std :: hang -
std :: sleep -
std :: stop -
std :: pause -
std :: suspend -
std :: freeze -
std :: busy -
std :: stall -
std :: restrain -
std :: hamster_wheel -
std :: beach_ball -
std :: chill_pill -
std :: hold_your_horses -
std :: 🔁 -
std :: 🎡
7. Language Wording Option #1
Modify [intro.progress] as follows:
The implementation may assume that any thread will eventually do one of the following:
terminate,
- call a function marked
,
[[ noreturn ]] - call
,
std :: this_thread :: yield () make a call to a library I/O function,
perform an access through a
glvalue, or
volatile perform a synchronization operation or an atomic operation.
[Note: This is intended to allow compiler transformations such as removal , merging, and reordering of empty loops, even when termination cannot be proven. —end note]
Notwithstanding the above, the implementation must implement an iteration statement ([stmt.iter]) by a call toif this iteration statement:
std :: this_thread :: halt () [Note: This is intended to allow programmers to use idiomatic trivial infinite loops without these loops being Undefined Behavior per the previous clause. —end note]
does not perform one of the above, and
the iteration statement’s controlling expression is a converted constant expression ([expr.const]) that converts to
true
, where the controlling expression is the condition of aor
while loop, or the
for of a
expression /
do loop, and
while the iteration statement contains none of:
a top-level
statement,
break a
statement which goes out of the loop,
goto a
,
return a
statement,
co_return a
expression,
co_await a
expression, and
co_yield the iteration statement doesn’t contain any of:
an exception being thrown,
a call to
.
std :: longjmp ()
8. Language Wording Option #2
Modify [intro.progress] as follows:
The implementation may assume that any thread will eventually do one of the following:
terminate,
- call a function marked
,
[[ noreturn ]] - call
,
std :: this_thread :: yield () make a call to a library I/O function,
perform an access through a
glvalue, or
volatile perform a synchronization operation or an atomic operation.
[Note: This is intended to allow compiler transformations such as removal , merging, and reordering of empty loops, even when termination cannot be proven. —end note]
Notwithstanding the above, the implementation must implement an iteration statement ([stmt.iter]) by a call toif this iteration statement:
std :: this_thread :: halt () [Note: This is intended to allow programmers to use idiomatic trivial infinite loops without these loops being Undefined Behavior per the previous clause. —end note]
does not perform one of the above, and
the iteration statement’s controlling expression is a converted constant expression ([expr.const]) that converts to
true
, where the controlling expression is the condition of aor
while loop, or the
for of a
expression /
do loop, and
while the iteration statement’s statement is empty.
9. Effect
Here are examples of the effects of this proposed change:
Code | Current equivalence in C++ | Current equivalence in C | Equivalence with Language Wording #1 | Equivalence with Language Wording #2 | Note |
---|---|---|---|---|---|
|
undefined behavior
| infinite loop (same as )
|
|
| Idiomatic trivial infinite loop |
|
undefined behavior
| infinite loop (same as )
|
|
| Idiomatic trivial infinite loop |
|
undefined behavior
| infinite loop (same as )
|
|
undefined behavior
| Trivial infinite loop, including a meaningless statement in the loop body |
|
undefined behavior
|
undefined behavior
|
undefined behavior
|
undefined behavior
| The iteration statement’s controlling expression isn’t a constant expression which converts to true
|
|
undefined behavior
| infinite loop (same as )
| infinite loop (same as )
| infinite loop (same as )
| The iteration statement’s controlling expression is a constant expression which converts to true
|
|
undefined behavior
| infinite loop (same as )
|
undefined behavior
|
undefined behavior
| Contains , the iteration statement’s controlling expression is a constant expression which converts to true
|
|
undefined behavior
| infinite loop (same as )
| infinite loop (same as )
|
undefined behavior
| The is unevaluated, the is therefore not relevant
|
|
unchanged (Undefined Behavior if doesn’t contain a side-effect)
|
unchanged (Undefined Behavior if doesn’t contain a side-effect)
|
unchanged (Undefined Behavior if doesn’t contain a side-effect)
|
unchanged (Undefined Behavior if doesn’t contain a side-effect)
| might contain a side-effect, the loop cannot be assumed to be infinite
|
|
undefined behavior
|
unchanged
|
unchanged
|
unchanged
| a loop without side-effects which nonetheless yields provides forward progress |
10. Alternative
An alternative would be to specify something along the lines of:
The implementation may assume that any thread will eventually do one of the following:
terminate,
- call a function marked
,
[[ noreturn ]] - call
,
std :: this_thread :: yield () make a call to a library I/O function,
perform an access through a
glvalue, or
volatile perform a synchronization operation or an atomic operation.
[Note: This is intended to allow compiler transformations such as removal , merging, and reordering of empty loops, even when termination cannot be proven. —end note]
Notwithstanding the above, a program containing an iteration statement’s controlling expression is a converted constant expression ([expr.const]) that converts totrue
, where the controlling expression is the condition of aor
while loop, or the
for of a
expression /
do , which is dynamically executes, but which does not contain one of the above, has no forward progress guarantee until the iteration statement terminates, at which point its forward progress guarantees are restored.
while
This approach would cast a wider net, and allow SIMT implementation or cooperative multithreading implementation on a uniprocessor to fail to manifest forward progress on long-running loops which don’t have side-effects yet do terminate.