llvm dev - Mar 2013 - [LLVMdev] Does a recursive call have side effects?

Currently LLVM removes infinite recursion in readnone functions as dead code. 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.

-Andy

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