[LLVMdev] Tail calls (TCO) in PNaCL | PNaCl Bitcode reference manual

[Travis Cross]

On 2013-07-30 22:11, Eli Bendersky wrote:
> we've published an initial version of the PNaCl bitcode reference
> manual online -
> http://www.chromium.org/nativeclient/pnacl/bitcode-abi. The PNaCl
> bitcode is a restricted subset of LLVM IR.
> 
> Any comments would be most welcome.

Hi Eli,

I appreciate you for opening the process for input and comments.  One
question stood out to me while reading the document:

The document [1] indicates that only the 'ccc' calling convention will
be supported.  The LLVM documentation [2] prominently notes that,
"tail calls can only be optimized when [fastcc], the GHC or the HiPE
convention is used."  Further, I notice that the document includes
"call" but not "tail call" in the list of supported instructions.

Do I understand correctly that this means that reliable tail call
optimization will not be possible under PNaCL as currently imagined?

That would be a real shame.  Languages such as Scheme, Haskell,
Erlang, and Lua require tail call optimization.  Working around the
lack of TCO with trampolines degrades performance, requires a major
reworking of the compiler front-end, and is ugly.  Such hacks really
shouldn't be needed in 2013, particularly when LLVM already went to
the trouble of supporting TCO for exactly these good reasons.

The JVM made this mistake in its byte code and many groups such as the
Clojure and Scala communities have been clamoring for years to get TCO
into the JVM.  ECMAScript has this error as well, but it's forgivable
as Javascript wasn't originally intended to be, as it is now, a
compiler target.

Indeed, I believe much of the enthusiasm for (P)NaCL stems from the
hope that we'll finally be able to compile arbitrary languages for the
browser without being unduly hampered or constrained.  Without TCO the
excitement here would be diminished.  Functional programming languages
would be kneecapped by the bytecode.

If my understanding above is correct, how can we get PNaCL to support
a sufficiently general calling convention to make TCO possible?

The "Stability of the PNaCl bitcode ABI" [3] document notes that the
translator will be restoring the fastcc convention (though issue #2346
notes this may only happen after the first release).  Perhaps we could
support the "tail call" instruction and have the translator ensure an
appropriate calling convention is restored when that is seen?  Or
perhaps we could revisit our reluctance to support multiple calling
conventions?  Or perhaps we could address the issues with fastcc that
are causing us to reject it, or create a new calling convention that
is simultaneously acceptable for our needs and supports TCO?

Certain individuals who I judged might be interested in working out a
solution here were CCed on an otherwise identical version of this
message that did not go out to the list.

Thanks,

-- TC

[1] http://www.chromium.org/nativeclient/pnacl/bitcode-abi

[2] http://llvm.org/releases/3.3/docs/LangRef.html#callingconv

[3] https://sites.google.com/a/chromium.org/dev/nativeclient/pnacl/stability-of-the-pnacl-bitcode-abi