I was hoping for a discussion in P2809 of why C++ can’t “just” adopt C’s version of the rule, but I didn’t find one.
The forward progress guarantee seems weird to me. I understand its value as a property of the infrastructure on which the program is running (the locking primitives, the scheduler, etc.) but I don’t understand why it’s necessary to extend the requirement to programs that don’t necessarily need or want that guarantee.
The idea is that you can implement multi threading in C++ in user space without parallelism by context switching at an observable checkpoint (e.g. I/O, volatile, synchronization primitive).
That way you can just round-robin between threads and it is not observable that you don't actually have parallelism.
If you just allow infinite loops, one thread being stuck would prevent the other ones from making progress. So instead, a subset of them are transformed into essentially repeated yield calls.
I don't see how that's nearly strong enough motivation to make this UB.
First of all, only a small fraction of programs will actually be executed in such a way, but the fwd progress UB is something every C++ programmer needs to deal with.
Secondly, if we compare Rust (no "UB for infinite loops" of any sort) with C++ for this usecase, we have:
Program where all loops terminate or have a side-effect: same in both languages
Program has an infinite loop without a side-effect: full UB in C++, stuck program in Rust
The full UB can lead to the compiler reordering things in ways that make debugging this a nightmare. I'll take the Rust variant of this over the C++ variant any day.
A program with an infinite "pure" loop has a liveness bug, yes. But I think it is a terrible idea to turn that liveness bug into UB. That kind of bug amplification is completely misguided IMO.
How does Rust handle infinite loops? The reason that they're UB in C/C++ is that they make a load of seemingly simple optimisations unsound. Most optimisations that move things from loop bodies or before a loop to after a loop are sound on the assumption that the loop eventually terminates. If the loop is permitted to never terminate, these transforms are unsound. These are very simple transforms to state and so have been done by most compilers for decades but the implicit assumption is always that loops terminate. This also means that functions can be assumed to eventually return (C and C++ now have attributes for explicitly stating that they don't).
If the language says infinite loops are permitted then the compiler can do these transforms if and only if it can statically prove that the loop terminates. This is impossible in the general case and turns out to be very hard in a bunch of other cases.
If anything, I'd have thought that Rust's ownership model increased the set of loops that can't be statically proven to not terminate but can be statically proven to not have globally-visible side effects, since most Rust loops can be statically proven to not mutate aliased state, which makes this assumption more important.
This was actually broken for a long time in Rust, meaning you could get UB-like behavior from safe code such as loop { } (In a language-lawyery way, it was not UB, simply because the language says safe code has no UB. In a practical way, it behaved exactly like it). The reason was that LLVM had indeed baked the assumption that loops eventually terminate or do side-effects deeply into its optimizations.
However, starting with LLVM 12, that assumption is no longer hardcoded, or even the default. You need to use the mustprogress attribute to indicate to LLVM that it can assume forward progress. What rustc does now is simply not emit that attribute, just like Clang does for loops whose controlling expression is an integer constant expression. Of course, if the compiler frontend can statically prove that the loop eventually makes progress, it can still soundly emit that attribute, but then LLVM itself is pretty good at control flow analysis too so maybe it would just figure that out anyway.
So tl;dr how Rust handles infinite loop without side effects is to completely remove the UB (which is basically forced by the design constraint that safe code has no UB) and to eat the potential missed optimizations.
Is there any data on how much this costs in terms of performance? I'd be surprised if it's small given how fundamental the transforms that it enables are to enabling later optimisations.
I'm also somewhat curious of the extent to which LLVM actually skips doing optimisations if they're unsound in the presence of infinite loops. Given that none of these transforms are formally verified, I wouldn't be surprised if it's still doing all of the transforms under unsound assumptions, just not folding infinite loops to trap.
When we looked at this for another language, our conclusion was that we'd impede too many optimisations if the compiler had to prove that every loop it wanted to move data across would terminate.
I don't remember any dent in our performance metrics from when we updated to a version of LLVM that fixed the infinite loop miscompilations. But that only measure the performance of the compiler itself.
I don't know about the data, sorry. I would also be really interested in reading about this.
To this point:
Given that none of these transforms are formally verified
There is the alive2 project that aims to do this, and it's already found a ton of bugs in translation passes. I'm not sure whether we can call any of them "formally verified" yet, though.
Alive2 is great, but it handles peephole optimisations, not those that modify the order of instructions. To formally verify these, you'd need a formal model of LLVM IR semantics.
I think Alive2 does have a formal model of a limited subset of LLVM IR. It's expressed in Z3 though. And I think VeLLVM has Rocq formalizations of some LLVM IR too. I personally would love a more complete formal model. I wonder if given AI etc etc we could create a formal model more easily.
I wonder if given AI etc etc we could create a formal model more easily.
Not really, no. The hard part is actually making all the choices that must be made to obtain an unambiguous formal model, and ensuring that the desired optimizations are compatible with these choices. Sometimes you find out that two optimizations need conflicting choices and then you're having a fun day (and some miscompilations).
We handle them by properly preserving their behavior, and guaranteeing they will loop forever. LLVM handles this correctly. There are some optimizations that only work if a loop terminates, but certainly not most of them, and I would not call any of them simple. Also, the loops that most need such optimizations (iterating loops that should be vectorized) are typically trivial for the compiler to prove termination.
There are some optimizations that only work if a loop terminates, but certainly not most of them, and I would not call any of them simple
Many of the cases of loop-invariant code motion and a lot of the corner cases of loop unswitching are unsound in the presence of infinite loops. Unless something has changed recently, these don't pay attention to the mustprogress attribute.
I think that's just not correct, most LICM is completely correct even for infinite loops. The hard case are loops that are never executed; the C++ UB does not help here (but Rust's assumptions about reference types do). What is an example of a case of LICM that is wrong for infinite loops?
Loop unswitching indeed often needs a termination proof -- and a proof that nothing in the loop has a side-effect, which is hard to get by even in C++ the moment any unknown functions are called. So this optimization already needs the compiler to have full visibility into everything that happens in the loop body. I would not call that a "simple" transform, and as I said in many cases, especially for iteration loops that really want to be auto-vectorized, the compiler can use its knowledge of the full loop body to fairly easily prove termination and then do unswitching. I am fairly sure LLVM checks mustprogress here; if it does not, please file a bug as that's clearly wrong.
So far I am not aware that Rust would suffer relevant performance in real-world use-cases due to this choice. (It's not really a choice, it's pretty much the only option for a memory safe language. Safe code can write infinite loops, so infinite loops must be well-behaved.) However I am also not sure if anyone studied this systematically.
What's an example of an optimization that's unsound for an infinite loop but sound for a loop that terminates in several weeks? Does it matter if the loop is yielding processor time or not?
yeah, for all the llvm is a "generic compiler backend" it is really geared around C/C++ semantics. e.g. null dereferences are UB through out the optimization pipeline, because it's ub in C.
There is the "null dereference is not UB" model (you get it from -fno-delete-null-checks in clang), but that's super conservative. The model it presents is that null pointers are valid pointers, which means if you have:
int *p = ...;
*p = ...;
if (!p) { ... }
Does not remove the null check (the model is null is a valid address to access, so the dereference proves nothing about the value).
Note that the actual UB-ness around null pointers in C/C++ does make sense in totality, e.g
int *p = 0;
int *q = p + 100;
*q = 1;
q is not the null pointer, but the result is UB because the dereference is fundamentally a null dereference - which is more clear when you think about it as being p[100] = 1.
It's gotten a lot better though. Rust has much less UB than C and C++, especially around (raw) pointer use, and we can use LLVM for this just fine these days.
I actually encountered this UB at an embedded systems job, where the assert handler tried to enter an infinite loop but instead ran off the function and crashed the program in a much less nice way. The crash handler also then tried to infinite loop, with the same fate...
The zero-cost cross-platform workaround I found was something like the following (been a minute, can't recall the exact syntax):
Hmm, I'm not sure this is an improvement all things considered. Yes it removes UB from infinite loops but only in "trivial" cases, and the definition of trivial seems a bit non-trivial. Worse, they use a different definition than C (even showing examples in the paper of loops that are fine in C but will continue to be UB in C++26).
So there is technically less UB but the edge has become more jagged and the cognitive load to avoid it is more. It can be better to have a somewhat overly restrictive rule that is easier to remember and follow.
I do like that they threw a bit of heat in the paper:
goto, setjmp/longjmp, 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.
fanf | a day ago
I was hoping for a discussion in P2809 of why C++ can’t “just” adopt C’s version of the rule, but I didn’t find one.
The forward progress guarantee seems weird to me. I understand its value as a property of the infrastructure on which the program is running (the locking primitives, the scheduler, etc.) but I don’t understand why it’s necessary to extend the requirement to programs that don’t necessarily need or want that guarantee.
foonathan | a day ago
The idea is that you can implement multi threading in C++ in user space without parallelism by context switching at an observable checkpoint (e.g. I/O, volatile, synchronization primitive).
That way you can just round-robin between threads and it is not observable that you don't actually have parallelism.
If you just allow infinite loops, one thread being stuck would prevent the other ones from making progress. So instead, a subset of them are transformed into essentially repeated yield calls.
ralfj | 23 hours ago
I don't see how that's nearly strong enough motivation to make this UB.
First of all, only a small fraction of programs will actually be executed in such a way, but the fwd progress UB is something every C++ programmer needs to deal with.
Secondly, if we compare Rust (no "UB for infinite loops" of any sort) with C++ for this usecase, we have:
The full UB can lead to the compiler reordering things in ways that make debugging this a nightmare. I'll take the Rust variant of this over the C++ variant any day.
A program with an infinite "pure" loop has a liveness bug, yes. But I think it is a terrible idea to turn that liveness bug into UB. That kind of bug amplification is completely misguided IMO.
david_chisnall | 22 hours ago
How does Rust handle infinite loops? The reason that they're UB in C/C++ is that they make a load of seemingly simple optimisations unsound. Most optimisations that move things from loop bodies or before a loop to after a loop are sound on the assumption that the loop eventually terminates. If the loop is permitted to never terminate, these transforms are unsound. These are very simple transforms to state and so have been done by most compilers for decades but the implicit assumption is always that loops terminate. This also means that functions can be assumed to eventually return (C and C++ now have attributes for explicitly stating that they don't).
If the language says infinite loops are permitted then the compiler can do these transforms if and only if it can statically prove that the loop terminates. This is impossible in the general case and turns out to be very hard in a bunch of other cases.
If anything, I'd have thought that Rust's ownership model increased the set of loops that can't be statically proven to not terminate but can be statically proven to not have globally-visible side effects, since most Rust loops can be statically proven to not mutate aliased state, which makes this assumption more important.
muvlon | 21 hours ago
This was actually broken for a long time in Rust, meaning you could get UB-like behavior from safe code such as
loop { }(In a language-lawyery way, it was not UB, simply because the language says safe code has no UB. In a practical way, it behaved exactly like it). The reason was that LLVM had indeed baked the assumption that loops eventually terminate or do side-effects deeply into its optimizations.However, starting with LLVM 12, that assumption is no longer hardcoded, or even the default. You need to use the
mustprogressattribute to indicate to LLVM that it can assume forward progress. What rustc does now is simply not emit that attribute, just like Clang does for loops whose controlling expression is an integer constant expression. Of course, if the compiler frontend can statically prove that the loop eventually makes progress, it can still soundly emit that attribute, but then LLVM itself is pretty good at control flow analysis too so maybe it would just figure that out anyway.So tl;dr how Rust handles infinite loop without side effects is to completely remove the UB (which is basically forced by the design constraint that safe code has no UB) and to eat the potential missed optimizations.
david_chisnall | 21 hours ago
Is there any data on how much this costs in terms of performance? I'd be surprised if it's small given how fundamental the transforms that it enables are to enabling later optimisations.
I'm also somewhat curious of the extent to which LLVM actually skips doing optimisations if they're unsound in the presence of infinite loops. Given that none of these transforms are formally verified, I wouldn't be surprised if it's still doing all of the transforms under unsound assumptions, just not folding infinite loops to trap.
When we looked at this for another language, our conclusion was that we'd impede too many optimisations if the compiler had to prove that every loop it wanted to move data across would terminate.
ralfj | 20 hours ago
I don't remember any dent in our performance metrics from when we updated to a version of LLVM that fixed the infinite loop miscompilations. But that only measure the performance of the compiler itself.
muvlon | 21 hours ago
I don't know about the data, sorry. I would also be really interested in reading about this.
To this point:
There is the alive2 project that aims to do this, and it's already found a ton of bugs in translation passes. I'm not sure whether we can call any of them "formally verified" yet, though.
david_chisnall | 20 hours ago
Alive2 is great, but it handles peephole optimisations, not those that modify the order of instructions. To formally verify these, you'd need a formal model of LLVM IR semantics.
3lambda | 18 hours ago
I think Alive2 does have a formal model of a limited subset of LLVM IR. It's expressed in Z3 though. And I think VeLLVM has Rocq formalizations of some LLVM IR too. I personally would love a more complete formal model. I wonder if given AI etc etc we could create a formal model more easily.
ralfj | 18 hours ago
Not really, no. The hard part is actually making all the choices that must be made to obtain an unambiguous formal model, and ensuring that the desired optimizations are compatible with these choices. Sometimes you find out that two optimizations need conflicting choices and then you're having a fun day (and some miscompilations).
ralfj | 21 hours ago
We handle them by properly preserving their behavior, and guaranteeing they will loop forever. LLVM handles this correctly. There are some optimizations that only work if a loop terminates, but certainly not most of them, and I would not call any of them simple. Also, the loops that most need such optimizations (iterating loops that should be vectorized) are typically trivial for the compiler to prove termination.
david_chisnall | 20 hours ago
Many of the cases of loop-invariant code motion and a lot of the corner cases of loop unswitching are unsound in the presence of infinite loops. Unless something has changed recently, these don't pay attention to the
mustprogressattribute.ralfj | 18 hours ago
I think that's just not correct, most LICM is completely correct even for infinite loops. The hard case are loops that are never executed; the C++ UB does not help here (but Rust's assumptions about reference types do). What is an example of a case of LICM that is wrong for infinite loops?
Loop unswitching indeed often needs a termination proof -- and a proof that nothing in the loop has a side-effect, which is hard to get by even in C++ the moment any unknown functions are called. So this optimization already needs the compiler to have full visibility into everything that happens in the loop body. I would not call that a "simple" transform, and as I said in many cases, especially for iteration loops that really want to be auto-vectorized, the compiler can use its knowledge of the full loop body to fairly easily prove termination and then do unswitching. I am fairly sure LLVM checks
mustprogresshere; if it does not, please file a bug as that's clearly wrong.So far I am not aware that Rust would suffer relevant performance in real-world use-cases due to this choice. (It's not really a choice, it's pretty much the only option for a memory safe language. Safe code can write infinite loops, so infinite loops must be well-behaved.) However I am also not sure if anyone studied this systematically.
jjuran | 18 hours ago
What's an example of an optimization that's unsound for an infinite loop but sound for a loop that terminates in several weeks? Does it matter if the loop is yielding processor time or not?
gepardo | a day ago
Finally :)
Reminds me somehow how this C++ UB made into a bug in
rustcbecause of LLVM.olliej | a day ago
yeah, for all the llvm is a "generic compiler backend" it is really geared around C/C++ semantics. e.g. null dereferences are UB through out the optimization pipeline, because it's ub in C.
There is the "null dereference is not UB" model (you get it from
-fno-delete-null-checksin clang), but that's super conservative. The model it presents is that null pointers are valid pointers, which means if you have:Does not remove the null check (the model is null is a valid address to access, so the dereference proves nothing about the value).
Note that the actual UB-ness around null pointers in C/C++ does make sense in totality, e.g
qis not the null pointer, but the result is UB because the dereference is fundamentally a null dereference - which is more clear when you think about it as beingp[100] = 1.ralfj | 23 hours ago
It's gotten a lot better though. Rust has much less UB than C and C++, especially around (raw) pointer use, and we can use LLVM for this just fine these days.
olliej | 16 hours ago
Oh yeah, but largely as a consequence of rust and similar either directly fixing the issues or making it clearly unreasonable to not address them.
ralfj | 14 hours ago
Yeah, but IMO that's entirely reasonable. No point in prematurely generalizing for hypothetical languages nobody has an interest in actually building.
jlarocco | a day ago
As somebody who actually likes C++, I have to admit it's difficult sometimes.
Riolku | 18 hours ago
I actually encountered this UB at an embedded systems job, where the assert handler tried to enter an infinite loop but instead ran off the function and crashed the program in a much less nice way. The crash handler also then tried to infinite loop, with the same fate...
The zero-cost cross-platform workaround I found was something like the following (been a minute, can't recall the exact syntax):
muvlon | a day ago
Hmm, I'm not sure this is an improvement all things considered. Yes it removes UB from infinite loops but only in "trivial" cases, and the definition of trivial seems a bit non-trivial. Worse, they use a different definition than C (even showing examples in the paper of loops that are fine in C but will continue to be UB in C++26).
So there is technically less UB but the edge has become more jagged and the cognitive load to avoid it is more. It can be better to have a somewhat overly restrictive rule that is easier to remember and follow.
I do like that they threw a bit of heat in the paper:
fanf | a day ago
How impertinent to say this prizewinning masterpiece is not idiomatic! https://www.ioccc.org/1987/wall/index.html
aardvark179 | a day ago
It really is a surprisingly spicy paper.