4 ms·

Okay, can somebody explain?

• davikrr 5y ago
  "LLVM considers infinite recursion to be UB, so the only valid way for this function to execute is to return true"
  • Winsaucerer 5y ago
    What does 'UB' stand for?
    • the_only_law 5y ago
      Undefined Behavior
    • loeg 5y ago
      Undefined Behavior.
  • jasode 5y ago
    >"LLVM considers infinite recursion to be UB, Not sure why he used the word "recursion" since collatz() is not calling itself.
    • tpush 5y ago
      He means the general concept of recursion, of which looping is an implementation, so to speak.
    • forgetfulness 5y ago
      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.
  • tomhallett 5y ago
    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)?
    • detaro 5y ago
      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.
  • andrewaylett 5y ago
    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.
• GuB-42 5y ago
  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.
• josephcsible 5y ago
  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.