It depends on the simplicity of a condition and how it's written. You could write a binary search so that the compiler can see that it always terminates, but it wouldn't be the normal way to write it, etc. Many loops are not going to be verifiable as trivially terminating.
Conversation
Mutually recursive function calls are another case that's very difficult. In order to avoid treating every single function call as needing to have that universal side effect inserted (destroying tons of optimization), the compiler would have to analyze the call graph.
1
Even if the recursion isn't via guaranteed tail calls stack overflow is well-defined and safe in these languages. It CANNOT be replaced with arbitrary memory corruption. They're saying that even remotely safe languages should have significantly worse compile-time and performance.
2
I'm pretty cool with pessimizing recursion of all forms. Recursion is a bug. :-)
1
It's difficult for a compiler to know if it happens though. It would need to do whole program analysis to build a potential call graph to avoid being able to insert a massive number of these performance killing intrinsics. Indirect calls also make it much harder to figure it out.
1
It penalizes code without any recursion, because the compiler doesn't know that. You really just end up needing to do the same analysis LLVM should be doing yourself in the higher level compiler: an internal function attribute for always_returns and functions without it get this.
2
If a function is calling another function without a locally-visible definition, it can't be assumed to be pure anyway, no? If definitions are locally visible, potential for recursion is visible.
1
LLVM will go through the program and mark things as pure followed by bubbling that up. It has a function attribute pass responsible for bubbling up internal function attributes like noreturn, etc. It could do that with always_returns too.
1
So, LLVM is in a position to do this correctly already, in a way that's essentially ideal. Instead, they are just ignoring non-termination as an effect, and providing a painful and costly workaround for frontends that actually care about correctness.
1
They do have 'noreturn' and bubble it up, just no 'always_returns' or the opposite 'may_return' which would accomplish the same thing. Their optimizations treat 'noreturn' as an effect already too... and they aren't going to remove that, since it should be.
1
That's why in my example (gist.github.com/thestinger/139) removing the conditional return will stop the breakage from happening. LLVM considers 'noreturn' an effect but not a function that MAY be 'noreturn'. And they just come up with excuses / workarounds instead of a fix.
I honestly have absolutely no idea why they aren't just addressing it properly. The way they are doing it is wrong for C and C++ too, despite them portraying it and addressing it as if other languages simply need a different approach because LLVM is C centric. It's a red herring.
1
It's far from one of the most important of these issues, but I feel like it's an incredibly useful case study of how broken the development process and decision making for LLVM is. It's a nice simple, easily demonstrated example of what happens in much more complex cases.
1
Show replies