llvm dev - Aug 2013 - [LLVMdev] Tail calls (TCO) in PNaCL | PNaCl Bitcode reference manual

Hello,

Following an earlier email (
http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-June/063010.html), 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.

The reference manual is quite terse, so for the bigger picture I'll repost
links to the design document:
* PDF:
https://docs.google.com/a/chromium.org/viewer?a=v&pid=sites&srcid=Y2hyb21pdW0ub3JnfGRldnxneDo0OWYwZjVkYWFjOWNjODE1
* Text:
https://sites.google.com/a/chromium.org/dev/nativeclient/pnacl/stability-of-the-pnacl-bitcode-abi

Any comments would be most welcome. If anything isn't clear, please speak
up - we intend to improve the documentation incrementally. We're also
working on better formatting, so consider this an early preview :)

Eli
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130730/303d4759/attachment.html>

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

Hi Eli,

Recently, I proposed some changes to LLVM to do more lowering of illegal
types (like i128 or i17) and other things within the LLVM IR layer, and the
proposal was roundly rejected by the LLVM community:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-April/061567.html

PNaCl is essentially doing what my proposal described. How do you expect to
reconcile the community's desire to avoid doing lowering on LLVM IR with
PNaCl's design that is built on doing lowering on LLVM IR?

Dan


On Tue, Jul 30, 2013 at 3:11 PM, Eli Bendersky <eliben at google.com>
wrote:
> Hello,
>
> Following an earlier email (
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-June/063010.html),
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.
>
> The reference manual is quite terse, so for the bigger picture I'll
repost
> links to the design document:
> * PDF:
>
https://docs.google.com/a/chromium.org/viewer?a=v&pid=sites&srcid=Y2hyb21pdW0ub3JnfGRldnxneDo0OWYwZjVkYWFjOWNjODE1
> * Text:
>
https://sites.google.com/a/chromium.org/dev/nativeclient/pnacl/stability-of-the-pnacl-bitcode-abi
>
> Any comments would be most welcome. If anything isn't clear, please
speak
> up - we intend to improve the documentation incrementally. We're also
> working on better formatting, so consider this an early preview :)
>
> Eli
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130801/af57b0bc/attachment.html>

On 1 August 2013 10:19, Dan Gohman <dan433584 at gmail.com> wrote:
> Hi Eli,
>
> Recently, I proposed some changes to LLVM to do more lowering of illegal
> types (like i128 or i17) and other things within the LLVM IR layer, and the
> proposal was roundly rejected by the LLVM community:
>
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-April/061567.html
>
> PNaCl is essentially doing what my proposal described. How do you expect
> to reconcile the community's desire to avoid doing lowering on LLVM IR
with
> PNaCl's design that is built on doing lowering on LLVM IR?
>
I expect we'll have to continue maintaining our own integer lowering IR
pass for PNaCl, unless upstream LLVM has a change of heart and decides to
add an implementation of such an IR pass.

The pass isn't excessively complex so I don't think this will be a big
burden, although it does only handle increasing the integer size (e.g. i17
-> i32), and not splitting integers up (i128 -> two i64s).  Having this
pass certainly seems preferable to allowing arbitrary-sized integer types
in the PNaCl ABI.

Here's the current implementation of the pass:
http://git.chromium.org/gitweb/?p=native_client/pnacl-llvm.git;a=blob;f=lib/Transforms/NaCl/PromoteIntegers.cpp;h=017e4976f27d2557b67c3b563e3685d140517808;hb=b9657234ee8b1951db5977a8ffb55a2e5df6d76c

For comparison, Emscripten does much the same thing.  It has its own
integer legalisation pass, but it's implemented in Javascript rather than
in C++.

Cheers,
Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130801/ac2ad9d4/attachment.html>

On 1 Aug 2013, at 18:19, Dan Gohman <dan433584 at gmail.com> wrote:
> PNaCl is essentially doing what my proposal described. How do you expect to
reconcile the community's desire to avoid doing lowering on LLVM IR with
PNaCl's design that is built on doing lowering on LLVM IR?
I don't think that the problem was lowering in the IR, it was extending the
IR to support all of the machine-dependent types that would be needed to lower
for arbitrary target architectures.  PNaCL only has to lower for a specific
abstract architecture that only supports types that can already be represented
in the IR.

David

On 1 August 2013 00:11, 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."

That note in the documentation seems to be incorrect, because LLVM will do
tail call optimisations on at least x86 when using the "ccc" calling
convention.  For example:

$ cat tail_call1.c
void foo(int arg);
void bar(int arg) {
  foo(arg);
}

$ clang tail_call1.c -S -o - -O2
...
bar:                                    # @bar
...
    jmp    foo                     # TAILCALL
...

However, LLVM doesn't emit a tail call at -O0.

Maybe what the documentation means to say is that tail call optimisations
are only guaranteed to be done when using fastcc etc.?


Further, I notice that the document includes
> "call" but not "tail call" in the list of supported
instructions.
>
That's an omission in the document.  We do actually allow the "tail
call"
instruction in PNaCl.

However, we haven't specified any guarantees that a tail call optimisation
will happen.  I suppose we could specify some guarantees if people want
this.  Maybe we could say that a "tail call" instruction is guaranteed
to
be turned into a real tail call if the callee function has the same number
of arguments as the caller function or fewer?  I think that would work on
all the architectures PNaCl targets.

Then we would have to change -O0 translation so that the guarantee is
provided consistently at all optimisation levels.

Cheers,
Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130801/1719e45f/attachment.html>