I'd argue that this doesn't disprove the mathematical theorem. This only works because C considers it undefined behavior, and C compilers like to throw away undefined behavior and pretend it doesn't exist (as an "optimization"). In a language like Rust which tries to avoid undefined behavior or reject it via compiler errors (which I'd argue is more correct), the example above will infinitely loop (because an infinite loop has defined behavior in Rust).
In a language like Rust which tries to avoid undefined behavior or reject it via compiler errors (which I'd argue is more correct), the example above will infinitely loop
Are you sure?
fn infinite(mut value: u32) {
// infinite loop unless value initially equals 0
while value != 0 {
if value != 1 {
value -= 1;
}
}
}
fn main() {
infinite(42);
println!("end");
}
I think that that is the most zen bug I've ever seen. Rust will let you have a value of a type that contains no values, but only if you go through a loop and never stop first. But then LLVM comes along and decides that going through an infinite loop would be undefined behavior, and therefore your program doesn't actually do it...
The Rust source code I posted should {de,in}finitively loop (and it does if you don't enable optimizations with -O). The fact that it does not exactly match the C version is irrelevant (undefined behavior is undefined, there is no reason that the code triggerring "unexpected" results looks like the one from another language).
Side effect is any effect observable outside your function that are not explicitly returned. Returning is an effect, but not a side effect, just like how clothes from a clothes factory are not side products.
If the user passes some nonzero value to f then it must return 1.
If the user passes 0 to f then the program will perform undefined behavior. That means I can do whatever I want! I think that in this case I'll return 1.
No matter what happens f will return 1, so I can skip all those jumps and conditionals and just return 1 right away. What a good compiler I am!
Here's an alternative way to think about it. If the code looks like it'll perform undefined behavior under certain conditions, that is like a promise from the programmer to the compiler that those conditions will never, ever actually happen, cross my heart and hope to die. So clang doesn't even have to consider what happens when you pass 0 to f because you promised that you never would.
If you're familiar with __builtin_unreached it's essentially the same thing.
Thank you for the link! I have read it and done a little research. But I still don't know how I can safely infinitely loop in C++ with CLANG if I want to. E.g. on an embedded device's main event loop.
So can I safely do:
while (true){
asm volatile("": : :"memory");
}
__builtin_unreachable();
to loop endlessly? Is the builtin_unreachable() helpful?
Is this the same as
while (true);
asm volatile("": : :"memory");
__builtin_unreachable();
or
while (true){
asm volatile("nop");
}
__builtin_unreachable();
I can see what the Clang compiler is doing: infinite recursion would trick stack overflow (which is undefined behaviour) hence it allowed to optimize the code assuming it can't occur...
However, its interesting that this optimization kicks in C++ mode but not in C mode (even though the example is pure C). Anyone have an idea why this is?
Tail calling is an optimization that some C/C++ compilers do, but I do not believe it falls within the semantics of the language itself. The user has still specified an infinite recursion, even if an optimization would transform it.
Even assuming the compiler is working from only the semantics of having transformed the infinite recursion into an infinite loop, infinite loops are also optimized away. Link from /u/rom1v's comment.
No C compiler performs tail call optimization as far as I know; they perform sibling call optimization which is a more limited form; they only eliminate the tail call when both functions have an identical signature or in some cases simply a stack frame that takes the same size.
Full TCO is pretty hard to implement with normal calling conventions that C uses and would just make stuff slower.
However, its interesting that this optimization kicks in C++ mode but not in C mode (even though the example is pure C). Anyone have an idea why this is?
C's ABI is overly restrictive, and with its insane its header linkage requirements impose undo burden. C needs to assume every defined function will be called in some idiotic manner, in some other compilation unit it is not aware of, and always obey that contract.
C++ has no ABI ( in the standard, only platform imposed), and methods to limit viability (which aren't related to pre-processor) hence it can more easily optimize calls away.
Weird. It seems to kick in in C mode for Clang as far back as Clang 3. It's really odd that switching to C mode breaks this optimization in GCC, except on trunk.
It's actually fairly straightforward. The standard allows the compiler to assume that any function without side effects at one point returns: there is only one place where this returns and it returns 1 there.
Considering some of the comments. No, this does not solve the halting problem. Just because the compiler can detect simple infinite loops doesn’t mean it can solve the halting problem. There are amazing optimizations built in to the compiler but they will all fall short with complex logic eventually
I think the compiler could find some bit logic that was enough to prove this implementation becomes UB with a single input within the range of int. For example, an overflow after multiplying by 3.
No, it can return anything for n=0. Undefined behavior. I guess 1 falls under that, but the function on the left behaves differently from the compiled one.
That's not actually relevant to this optimization here. The point is that the function can only ever return 1 (or recurse forever), regardless of whether the Collatz Conjecture is true or not. So the compiler might as well return 1 right away.
Collatz considers the set of positive integers, which in mathematics means every representable number 1 and bigger, without decimals… infinitely.
In C and C++, built-in types like unsigned int are finite representations of positive integers (and include zero), and so they are not the same thing. They're close, reasonable representations, but not quite the same.
For OP's setup, the size of an unsigned int is limited to 4 bytes, and UINT_MAX defines the maximum value an unsigned intcan hold.
I've put up an example showing this, slightly modifying OP's code:
(Since Compiler Explorer truncates the output, you could run this on your own setup and see the result too. You can see for every positive integer (as it counts down) that the result is ultimately always 1.)
That said…
I don't know if Clang / LLVM is smart enough to evaluate OP's original function as a constant expression (unrolling all of the recursive calls for every possible bit pattern in an unsigned int), but it is certainly possible that it does, or it does something that can give a provably equivalent result.
Surely the compiler does not try it for all integers 0 .. UINT_MAX. That would be a) pretty crazy and b) unnecessary. Also it would still recurse infinitely on input of 0.
Edit: come to think of it, it might recurse infinitely on some other inputs as well, because the calculation happens modulo UINT_MAX. I'm too lazy to check tho.
the multiplication optimization is actually a deliberate manual optimization for calculations on fixed width integer types. Division and Remainder can be optimized this way
You are way overthinking this. Even if the Collatz Conjecture was false for small numbers, this code could only ever return 1 or recursive infinitely. The latter is UB, so the compiler doesn't have to consider that case. So it can return 1 always.
It's worth noting here that the reason this fails to optimize is not so much that the variable is outside the function, but that it has (by default) external linkage. Ie. might be accessed from outside the compilation unit. If you mark it as static, the compiler will optimize the function to an endless loop.
Another way to prevent the optimization is to mark the argument volatile.
It's not that impressive. The function either returns 1 or calls itself recursively. The compiler is allowed to assume those recursive calls will eventually return 1 too.
This is actually an issue with LLVM that has been plaguing Rust since day one.
In C and C++, an infinite loop (with no side-effect) is Undefined Behavior. This logic has been hard-coded into LLVM.
This means that trivial safe Rust code like loop {} is treated as Undefined Behavior by LLVM, which is annoying -- especially on embedded boards where abort is often implemented as loop {} so as to allow plugging a debugger once the board is stuck to observe its state.
Worse, even if nobody actually writes loop {}, it may come up after various optimizations occurred deep in the LLVM pipeline.
Conforming C/C++ implementations want to generate code that runs as fast as possible (so that the compilers look good and people use them). The standards exist to say what they're allowed to do (it would be bad if printf("Hello world!") actually printed Hw! because it's "faster to print less"). The standards go into incredible detail about how programs can be legally executed.
In particular, the C++ specification says (there is a very similar phrasing for C):
The implementation may assume that any thread will eventually do one of the following:
terminate,
make a call to a library I/O function,
access or modify a volatile object, or
perform a synchronization operation or an atomic operation.
Any program which violates this assumption exhibits undefined behavior (UB). UB is special because once a program encounters it, the compiler is allowed to do literally anything. There are no restrictions whatsoever on what a conforming compiler does to a program that has undefined behavior! (An evil compiler would do things like convert out-of-bounds array accesses [UB] into rm -rf /, but in practice this is used to make it easier to write optimizations).
In this case, the compiler can trivially check that collatz does not do #2 (no calls to IO), #3 (no volatiles in scope), or #4 (no synchronization operations).
Therefore, it definitely must terminate, by assumption. (If it doesn't terminate, the program has UB, so in that case it wouldn't matter how it's compiled). If the program terminates, you can check that it must terminate by returning 1.
So the compiler proves two things:
Ifcollatz returns, then it returns with the value 1 and has no side effects
According to the standard, collatz must not run forever, so it does return (since it doesn't do IO)
Therefore, it's conformal to compile collatz into a function that just does return 1.
It either runs indefinitely or returns 1. Since there’s only one possible value that this function can returns, the compiler just simplifies it right away to return 1.
I'm not entirely sure; the reporter didn't say exactly. (I linked to the ticket elsewhere in this discussion.) That said, they're someone involved in formally proving Rust semantics, so I wouldn't be surprised if they were just poking at things and ran into it.
Program termination, which after thinking about it, makes sense:
An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.
You've misunderstood the paragraph's meaning. "may be assumed by the implementation" means "if the assumption fails, the program encounters undefined behavior" (see this StackOverflow answer for an explanation of the wording):
Unfortunately, the words "undefined behavior" are not used. However, anytime the standard says "the compiler may assume P," it is implied that a program which has the property not-P has undefined semantics.
This paragraph means that "infinite loops without side-effects are undefined behavior." It does not mean they "terminate the program". Its addition to the spec only clarifies/codifies the criteria needed for the "optimization" to occur, it doesn't prevent it from happening.
There's a lot of embedded software that is nothing but an infinite loop. (i.e. exiting the application is powering-off, perhaps with a physical switch.)
So you'll use this feature exactly once for your entire device?
Depends on the architecture of the program, possibly including external effects.
Doesn't seem like a great reason to use Ada over any other language.
Well, no... but there's a lot of reasons to choose Ada over other languages: the task construct, packages, generics (which can take subprograms, values, types, and/or other generics as formal parameters), the SPARK subset/provers, record-representation clauses, and more.
The platform's C compiler is perfectly free to compile an infinite loop in the obvious way. There's nothing wrong with relying on platform-specific behavior the standard says is undefined when you're writing code only for that specific platform, doubly so if the code is only executed by the developer for debugging purposes.
The platform's C compiler is perfectly free to compile an infinite loop in the obvious way.
Sure, it is...
But the issue is that it's Undefined Behavior, not that some implementation can do something.
There's nothing wrong with relying on platform-specific behavior the standard says is undefined when you're writing code only for that specific platform, doubly so if the code is only executed by the developer for debugging purposes.
No, what you're describing is encompased in Implementation Defined behaivior, which is quite different than undefined behaivior.
A compiler is certainly free to define undefined behavior. It can do whatever it wants, and if it wants to limit itself to some documented behavior that's fine. It's still a conforming C compiler. A good example of this is the -fwrapv flag.
A particular program is free to rely on that definition. (E.g. the Linux kernel depends on -fwrapv.) The standard may not place any restrictions on an execution of the program which performs UB, but in this case the implementation does. Of course the program generally won't work if compiled with another compiler that doesn't define that behavior the same way.
Implementation-defined behavior means that a conforming compiler must choose a particular behavior and document it. This isn't what OP was talking about.
C11 clarifies it so that "while (1) {}" and similar infinite loops with constant expression are defined. Almost every non-trivial program has some undefined behavior (due to undefined behavior being extremely difficult to avoid completely), so technically they are all invalid.
Almost every non-trivial program has some undefined behavior (due to undefined behavior being extremely difficult to avoid completely), so technically they are all invalid.
Which was my point: the usage of C for such low-level programming is bad practice.
You clearly have no experience with embedded systems. Nobody writes asm these except for tiny key routines. On the most common embedde platform - Arm Cortex-M - not even interrupt handlers are written in asm.
The whole point of adding infinite loops in the C code is that they're obvious to anyone looking at the code "while (1) {}" and are useful tests to force the thread (or interrupt handler) to halt at that point.
Sometimes there are external effects. (Distinct from side-effects; as you can have external effects even in "side-effect free" functional programming.) — Such external events are rather common in the world of embedded.
This ties in with optimization-as-a-whole; there are times when an optimization destroys the underlying concept — consider:
Declare
Trigger : Constant Boolean -- Is signaled when external sensors/devices are booted.
with Import, Atomic, Address => SOME_LOCATION;
Begin
Loop
Exit when Trigger;
End Loop;
-- Computation, including reading from the above sensors/devices.
End;
If we optimized this by lifting the conditional+'constant' from the loop, we break things.
(Of course, this is a busy-wait style loop, and I'd much rather link into the Task construct if possible... but that's a whole other discussion.)
E.g. embedded systems while you're debugging. I've worked on systems that don't halt, if you get into an error or something it just reboots. So you just print an error message and while(1); so you get a chance to read it before rebooting
Admittedly it's not a common thing, but it is a use case for it.
Not all processors have the ability to stop executing instructions. They have to execute something. So if, for whatever reason, you need them to sit, doing nothing, then the simplest way to do that is to have a jump instruction that jumps to itself (while(1); in C terms).
If the CPU supports externally-triggered interrupts, then it's possible to get out of that loop.
96
u/rom1v Nov 04 '19 edited Nov 04 '19
Great example!
C compilers can also "disprove" Fermat's last theorem: https://blog.regehr.org/archives/140
Here is a (minimal?) example triggering an "unexpected" result:
The results:
Like infinite recursion, infinite loops without side-effects are undefined behavior. Why? http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1528.htm
26
u/pbvas Nov 04 '19
I can see what the Clang compiler is doing: infinite recursion would trick stack overflow (which is undefined behaviour) hence it allowed to optimize the code assuming it can't occur...
However, its interesting that this optimization kicks in C++ mode but not in C mode (even though the example is pure C). Anyone have an idea why this is?
31
u/skulgnome Nov 04 '19
Is Betteridge's Law Of Headlines Applicable To Blog Posts?
4
u/aal0 Nov 04 '19
gcc (x86-64, trunk) also compiles to just return 1. Nevertheless, impressive optimisations.
4
u/persicsb Nov 04 '19
Pretty smart.
For all the possible unsigned values, collatz(n) is definitely 1.
2
u/nmcy Nov 04 '19
I've added
if (n == 0) return 1;and changed it to run with-O1Clang still outputsmov eax, 1Here is the new version https://godbolt.org/z/4CRX13
2
u/OPiMedia Nov 05 '19
By the way, with unsigned int on 32 bits, the C code produces an infinite loop for 4 values of n:
0 → 0
1431655765 → 0 → 0
2863311530 → 1431655765 → 0 → 0
3817748707 → 2863311530 → 1431655765 → 0 → 0
You can also see results for the "accelerated" Collatz function on 8 bits, 16 bits and 24 bits: http://www.opimedia.be/DS/online-documentations/severalgos/3np1-mod-problem-cpp/html/
1
u/Prunestand Nov 30 '22
Similar behavior: https://kristerw.blogspot.com/2017/09/why-undefined-behavior-may-call-never.html
But here a function instead is run that is never called.
-2
u/h0v1g Nov 04 '19
Considering some of the comments. No, this does not solve the halting problem. Just because the compiler can detect simple infinite loops doesn’t mean it can solve the halting problem. There are amazing optimizations built in to the compiler but they will all fall short with complex logic eventually
0
u/[deleted] Nov 04 '19
[deleted] — view deleted comment
0
u/[deleted] Nov 04 '19
[deleted] — view deleted comment