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

[Eli Bendersky]

On Wed, Jul 31, 2013 at 11:55 PM, Travis Cross <tc at travislists.com> wrote:

> 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?
>

Not at all. The tail call elimination pass runs during mid-level
optimizations, before we strip calling conventions for PNaCl ABI
stabilization. The "tail" marker on calls is not forbidden in PNaCl.
However, it would be fair to say that we didn't invest a lot of effort into
making sure TCO works in all cases because TCO support for C and C++ in
LLVM is very rudimentary. For example, in LLVM 3.3 (the version the current
preview of PNaCl is based on), this is the implementation of
AllocaMightEscapeToCalls:

static bool AllocaMightEscapeToCalls(AllocaInst *AI) {
  // FIXME: do simple 'address taken' analysis.
  return true;
}

Michael Gottesman (+CC) improved this a couple of weeks ago - this area is
still work in progress. While we'll be happy to have other languages target
PNaCl, our current focus is on C and C++. Also see below.



> 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?
>

This is exactly the kind of feedback we're interested in, and the PNaCl ABI
is not set in stone. I'm glad that you went over the "stability" document;
it means you noticed that we don't preclude expanding the scope of the
bitcode in the future. We do plan to ensure backwards compatibility, but
features can be added. If you, or any other interested party, wants to
investigate compiling Haskell or some other functional language to PNaCl -
please go ahead. Feel free to contact us personally or on the NaCl mailing
lists (or even in llvmdev@ for issues that are strictly LLVM IR related)
w.r.t. any problems you encounter. If there are additional
modes/instructions/attributes that need to be added to the ABI, we'll
consider it taking into account all the other constraints.

Eli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130801/216e8688/attachment.html>