“Pack it in, mathematicians, someone owes LLVM a million bucks”

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by davikrr on Thursday August 19, 2021 @09:34AM (#28233630)

"LLVM considers infinite recursion to be UB, so the only valid way for this function to execute is to return true"

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by jasode on Thursday August 19, 2021 @10:06AM (#28233989)

>"LLVM considers infinite recursion to be UB,

Not sure why he used the word "recursion" since collatz() is not calling itself.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by forgetfulness on Thursday August 19, 2021 @11:23AM (#28235016)

It's in the computability theory sense, since compilers and language specifications are symbolic math-heavy, and in math you model all these things as recursive functions, the terminology is applied uniformly.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by tpush on Thursday August 19, 2021 @10:29AM (#28234259)

He means the general concept of recursion, of which looping is an implementation, so to speak.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by Winsaucerer on Thursday August 19, 2021 @09:50AM (#28233798)

What does 'UB' stand for?

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by loeg on Thursday August 19, 2021 @09:56AM (#28233866)

Undefined Behavior.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by the_only_law on Thursday August 19, 2021 @09:51AM (#28233808)

Undefined Behavior

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by tomhallett on Thursday August 19, 2021 @11:14AM (#28234892)

How does LLVM decide this loop is unbounded? Is any `while(true)` loop considered UB and therefore replaced with `return true` or is there more advanced introspection of the ast (some limited set of the halting problem)?

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by detaro on Thursday August 19, 2021 @12:15PM (#28235700)

It checks how the loop can be exited, assumes that the loop must exit and thus take the code path that exits it, and then applies optimizations to remove everything it doesn't need to find the result.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by andrewaylett on Thursday August 19, 2021 @11:41AM (#28235252)

Which isn't quite right: the C++ spec allows the compiler to assume that a loop without side-effects will terminate. And the only way the loop terminates will be by returning true.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by GuB-42 on Thursday August 19, 2021 @11:38AM (#28235218)

The Collatz conjecture is saying that the programmed algorithm will eventually terminate and return true. Here the compiler optimized the code to always return true. Therefore the author jokingly assumed that the compiler must have proven the Collatz conjecture and the authors should be rewarded a million dollars.

In reality, the reason is that out of the two outcomes: true or infinite loop, the infinite loop violates the standard, and therefore, the result must be true. Another way to see it is that the only way for the code to be valid is if the programmer knows that the Collatz conjecture is true, and the compiler trusts the programmer, saying that the compiler knows the answer to the Collatz conjecture is a kind of circular reasoning.

There are other issues here: the numbers are bounded (a 128 bits integer), but the conjecture is not. And no million dollar prize have been assigned to this problem (it is not one of the millenium problems). Also, an infinite loop is not a result, it is actually the textbook example of an undecidable problem.

[ Parent | on HN ]

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by josephcsible on Thursday August 19, 2021 @01:25PM (#28236692)

Here's the relevant part of the C++ standard:

> 6.9.2.2 Forward progress [intro.progress]

> 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 volatile glvalue, or

> — perform a synchronization operation or an atomic operation.

That loop doesn't ever do any of the second through fourth things, and if it didn't return true, then it would never terminate either, so Clang is allowed to assume that it will eventually return true. And since the loop doesn't have any other effects visible outside the function, it can be optimized away entirely.

[ Parent | on HN ]