[LLVMdev] Does a recursive call have side effects?

[Chris Lattner]

On Mar 8, 2013, at 5:35 PM, Andrew Trick <atrick at apple.com> wrote:
> Currently LLVM removes infinite recursion in readnone functions as dead code.

See also the discussion in:
http://llvm.org/bugs/show_bug.cgi?id=965

> I assume this falls under the same language rules that allow removal of infinite loops. But I need to be certain. Can someone confirm? Standard citations welcome.
> 
> Otherwise this is wrong:
> 
>  bool mayHaveSideEffects() const {
>    return mayWriteToMemory() || mayThrow() || !mayReturn();
>  }
> 
> Note: For non-C support, it would be nice to have another attribute, maynotreturn (in C everything is mustreturn by default). In theory, if we had that, the C frontend could use it for potentially recursive calls, forcing the optimizer to either prove it's not recursive or consider it to have side effects. But if the function had nontrivial loops, the optimizer won't be able to remove the attribute. In practice, I think we just want to hide behind the standard with the old undefined behavior excuse and tell people who want infinite recursion to dereference a volatile.

I think that everyone agrees that this is incorrect behavior, but it is very corner-case and easily worked around.  It is also not clear how to fix this without overly pessimizing the optimizer.  For example, the most obvious way to fix this would be to add a "known-to-always-return" attribute (which would be inferred/propagated) and make calls to functions without this attribute be assumed to have side effects.  The problem is that we would only rarely be able to infer this property, so we wouldn't be able to do a lot of useful optimizations. 

-Chris