In C++ loops such as
for(;;) {}
used to be undefined behavior prior to P2809R3. Trivial infinite loops are not Undefined Behavior, whereas they are not in C(?).
In the aforementioned proposal, it is expressed that there were good reasons for undefined behavior in this case. Are there any simple examples to make that clear?
The reasons are optimizations only.
If the compiler can assume that all loops without side effects terminate, it does not have to prove that.
If the non-terminating loops were allowed, the compiler would be allowed to perform certain optimizations only if it could prove termination, that is impossible in general so it would turn into pattern recognition game. And for what benefit?
The underlying issue is that non-termination is a kind of side effect on itself. Any observable effect which is certain to happen after the loop terminates is observed if and only if the loop terminates, even though the loop doesn't have any effects.
Of course exactly the same reasoning can be done for if(expr) return;. The compiler is not allowed to move stuff after the if before if unless it can prove expr is false. But if is the fundamental control flow mechanism while non-terminating loops are not (IMHO).
Take the following code.
int collatz_conjecture(int i){
while(i!=1){
if ((i%2)==0)
i/=2;
else
i=i*3+1;
}
return i;
}
int main(){
collatz_conjecture(10);
return 5;
}
With -O3, gcc compiles it to:
collatz_conjecture(int):
mov eax, 1
ret
main:
mov eax, 5
ret
So, did the compiler prove the Collatz conjecture in order to determine that it should return 1 for all numbers? Of course not, that is just one of the optimizations allowed by termination assumption (and where UB can happen). The only way the loop can terminate is if i==1 therefore it can assume i==1 after the loop and use it for further optimizations -> the function always return 1 and can thus be reduced to it.
More useful example can be interleaved copy. If you have
loop A
loop B
the compiler is allowed to interleave them even without knowing that A terminates. Many vectorization operations rely on this assumption.
Similarly, reordering of some independent after-loop operations before the loop assumes the loop will terminate.
int range, (before overflow of int, so another UB) ;-) –
Gunnar gcc/g++ makes the desitintion between C and C++, whereas clang/clang++ produces the same code. So: ist clang wrong here? –
Demars collatz_conjecture(10); at compile-time and throw it away then. But since it works also for 10000000, then I guess it assumes termination. As I said, it is very reasonable assumption so I would not be too surprised for clang to be non-compliant in this regard because it is for good reasons. –
Fecundity collatz_conjecture() doesn't always use the return value, letting a compiler omit the loop in cases where the return value is ignored would be a useful optimization. Letting compilers make assumptions about things that would need to be true in order for a loop to terminate, however, would be counter-productive for most kinds of tasks compared with letting programmers rely upon control and data dependencies which are downstream of a loop's single statically reachable exit point. –
Doubly collatz_conjecture a static function ;-) –
Gloriane loop {} as the implementation of abort on small embedded platforms. So while optimizations may be the reason for making lack of progress UB, it's arguable whether it is a good reason, as C/C++/Rust programs tend to perform on par.. –
Mylo A[i] += C[i] and B[i] += C[i], with __restrict qualifiers to promise non-overlap, neither GCC nor Clang actually take advantage: godbolt.org/z/djM4eKsdP –
Angadreme while(1) { if(i==1)break; ...} godbolt.org/z/b615s5j1n shows the difference with g++ -xc (C) vs. g++ (C++). Hrm, as C, GCC doesn't assume while(i!=1) terminates. –
Angadreme mov eax, 1 for the while(i!=1) version, but a loop for the while(1) { if()break; ... version in C. And it assumes termination for both versions in C++. So Clang demonstrates the limit of how aggressive a compiler can be about this in C. GCC may just disable that optimization for C if it can't make it conditional on the loop condition being a constant expression. (See also How do I make an infinite empty loop that won’t be optimized away? - older clang got this wrong) –
Angadreme x < 65536 with (__ARTIFIAL_DEPENDENCY(i), 1), but only if it hadn't eliminated the loop that computes i, and after making that substitution it would not be able to omit the loop. –
Doubly #pragma omp simd reduction(foo:+) to tell a compiler it can pretend FP math is associative for foo += stuff in this one loop. The code in your answer, where GCC removes the infinite loop and the bounds-check in C++ mode but not C, certainly seems undesirable, although allowed by ISO C since x > 65535 will encounter infinite-loop UB. I guess it's just an artificial example of GCC making a bug worse, from hanging to out-of-bounds access, and such bugs could happen in real code. Clang keeps the bounds check when removing the loop: godbolt.org/z/3EshfzxqW –
Angadreme loop {} is an infinite loop (since there's no statement inside stopping it), and while true {} or for _ in std::iter::repeat(()) {} are other examples of infinite loops in the language. It was a battle teaching LLVM that this should not be optimized away, as far as I remember. –
Mylo while(i != 1) can also be infinite (unlike ISO C), but you're clearly saying yes to that, even though all your examples are things that would also be well-defined in C like while(1){} where the loop-condition is a constant expression (unlike C++). (Apparently the process of teaching LLVM about this rule did let it make that distinction in C, even if it didn't need to for Rust.) –
Angadreme i=-1 it will never reach i==1 and will never overflow (it will loop -1 => -2 => -1). There are other loops for non-positive inputs (the most trivial is when starting with 0) –
Appendant The primary benefit is simplicity of specification. The as-if rule cannot really accommodate the notion that a program can have behavior which is defined and yet may be observably inconsistent with sequential program execution. Further, the authors of the C and C++ Standards use the phrase "Undefined Behavior" as a catch-all for situations where they didn't think it necessary to exercise jurisdiction, in many cases because they expected that compiler writers would be better placed than the Committee to understand their customers' needs.
Most of the useful optimizations which are facilitated by specifying that if no individual action within a loop would be sequenced relative to some later piece of code, execution of the loop as a whole need not be treated as sequenced either. This is a bit "hand-wavy" with regard to what code comes "after" an endless loop, but it makes clear what it would allow a compiler to do. Among other things, if no individual action within a loop would be sequenced before program termination, then execution of the loop as a whole may be omitted entirely.
An important principle that such a rule would embody, which is missing from the present rule, is that a transform that would introduce a dependency between code within a loop and code outside the loop would also introduce a sequencing relationship. If a loop would exit if a certain condition is true, and code after the loop checks that condition, a compiler may use the result from the earlier check to avoid having to repeat the test, but that would mean that code after the loop was relying upon a value computed within the loop.
A concrete example which illustrates the useful and reckless ways the rule can be applied is shown below:
char arr[65537];
unsigned test(unsigned x, unsigned y)
{
unsigned i=1;
while((i & y) != x)
i*=17;
return i;
}
void test2(unsigned x)
{
test(x, 65535);
if (x < 65536)
arr[x] = 2;
}
There are two individually-useful optimizations that a compiler could apply when in-lining test into test2:
A compiler could recognize that a test to see whether x == (i & 65535) could only report "true" in cases where x is less than 65536, rendering the if test that in test2() redundant.
A compiler could recognize that because the only effect of the loop is to compute i, and the value of i will end up being ignored when test() is invoked from within test2(), the code for the loop is redundant.
Eliminating the loop while keeping the isolated if would likely be better than doing the reverse, but the ability of code to uphold what's likely a fundamental requirement--that it not write arr past element 65535--is reliant upon either the loop or the if test being retained. Either would be redundant in the presence of the other, but the absence of either would make the other essential.
Note that giving compilers the freedom to resequence code while keeping data dependencies would not preclude the possibility that a correct application might get stuck in an endless loop when fed some possible inputs, if the need to terminate the application using outside means in some cases would be acceptable. Allowing them to resequence code without regard for the resulting data dependencies, however, will have the ironic effect of speeding up primarily "erroneous" programs that cannot be relied upon to satisfy application requirements, and offer no benefit to most programs that add extra checking or dummy side effects (which would not otherwise be needed to satisfy application requirements) to guard against endless loops.
PS--as a further example of the general concept of two pieces of code being individually redundant in the presence of the other, consider the following functions:
double x,y,z;
void f1(void) {
x=sin(z);
}
void f2(void)
{
f1();
y=sin(z);
x=0;
}
The assignment x=sin(z); is redundant in the code as written, and could be optimized out, since nothing uses the value stored into x. The computation of sin(z) within f2 is redundant in the code as written, and could be replaced with y=x; since x will already hold the value that needs to be stored into y. It should be obvious, however, that the fact that either transformation could be legitimately applied by itself does not imply that both may be legitimately applied together. The idea that this principle should apply to the kinds of optimization used in the first example snippet would probably have been obvious to the people who wrote the Standard, but unfortunately not to the people who wrote clang and gcc.
gcc -fno-strict-aliasing defines the behaviour of *(int*)&my_float, and MSVC always defines the behaviour (it doesn't have an option to enable type-based alias analysis.) And gcc -fwrapv defines the behaviour of signed integer overflow as 2's complement wrapping. GCC (and the CPUs it compiles for) also define the behaviour of data races on volatile objects; the Linux kernel (and some pre-C++11 multi-threaded code) relies on that. –
Angadreme In both C and C++, endless loops without side effects exhibit undefined behavior. However, there might be slight differences in how compilers handle this situation between the two languages. Ultimately, relying on undefined behavior in either language is not recommended, as it can lead to unpredictable outcomes. It's best to avoid writing code that intentionally relies on undefined behavior.
© 2022 - 2025 — McMap. All rights reserved.
for (i=0;i<9;++i) ;for not having any effect (except settingi = 10, maybe), it might also optimize away similar infinite loops (unless an exception has been coded). To evaluate the side-effect of the loop as whole, the compiler has to examine the state after the loop (which, per definition, does not exist after an endless loop). Also as the loop never ends, it makes little sense to consider the statements after the loop. So maybe it's better to undefine the semantics... – Glorianewhile(true);is UB? – DisparateN1528in my answer which gives a rationale for this optimization. Also related to: https://mcmap.net/q/15528/-are-compilers-allowed-to-eliminate-infinite-loops – Neurology