[llvm-bugs] [Bug 47421] New: Clang should provide annotations to force or verify tail call optimization

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=47421

            Bug ID: 47421
           Summary: Clang should provide annotations to force or verify
                    tail call optimization
           Product: clang
           Version: unspecified
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: C
          Assignee: unassignedclangbugs at nondot.org
          Reporter: maxime.chevalierboisvert at shopify.com
                CC: blitzrakete at gmail.com, dgregor at apple.com,
                    erik.pilkington at gmail.com, llvm-bugs at lists.llvm.org,
                    richard-llvm at metafoo.co.uk

It's possible to use tail calls to implement bytecode interpreters in C/C++ in
a way that is much cleaner than with computed GOTOs, and potentially more
efficient as well. This is because, with computed GOTOs, you end up with a
large function body with very many labeled code blocks, such that every code
block can potentially jump to every other. This makes it hard for any compiler
to do register allocation effectively.

With tail calls, you can define a tail-recursive function for every opcode in
your interpreter such that every instruction simply calls the next one. Tail
calls also potentially give us a clean ABI (function call boundaries) where an
interpreter could efficiently dispatch to code generated by a JIT compiler.
However, this is only possible if one can ensure that tail recursion is in fact
optimized by the C/C++ compiler.

Clang currently does a fairly good job at optimizing tail calls, however, it's
not something developers can rely on. It happens behind the scenes, and to know
whether tail call optimization was performed or not, one has to carefully study
the disassembly. In our case, we have tried to convert the Ruby interpreter to
a tail recursive implementation, and found that tail call optimization was
performed for some, but not all Ruby opcodes. The Ruby codebase is very large,
which makes it difficult to tell which opcodes did not get optimized and why.

The usefulness of tail call optimization is clearly recognized in other
programming languages, but the fact that we currently can't rely on them
severely limits their usefulness. It would be very desirable to have some kind
of annotation to force the compiler to make specific function calls into tail
calls (eg: must_tail), or to force every control flow path leaving a given
function to become tail calls, or to at least produce a compilation error if
this cannot be done, so that the outcome is visible to the programmer.

I believe it's in the spirit of C to allow "unsafe" operations to be performed
if the programmer specifies this is what must happen, and so forcing tail calls
seems acceptable to me, so long as function call signatures are compatible, but
if that isn't possible, at least forcing a compiler error message (or even just
a warning) to be produced would already be a useful step forward.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200904/9d5853bd/attachment.html>