<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - Clang should provide annotations to force or verify tail call optimization"
href="https://bugs.llvm.org/show_bug.cgi?id=47421">47421</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Clang should provide annotations to force or verify tail call optimization
</td>
</tr>
<tr>
<th>Product</th>
<td>clang
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>C
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>maxime.chevalierboisvert@shopify.com
</td>
</tr>
<tr>
<th>CC</th>
<td>blitzrakete@gmail.com, dgregor@apple.com, erik.pilkington@gmail.com, llvm-bugs@lists.llvm.org, richard-llvm@metafoo.co.uk
</td>
</tr></table>
<p>
<div>
<pre>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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>