<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:600526394;
mso-list-type:hybrid;
mso-list-template-ids:-1332051296 -710100750 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:\F0D8;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:Arial;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:837117087;
mso-list-type:hybrid;
mso-list-template-ids:-684188426 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l2
{mso-list-id:1761019681;
mso-list-type:hybrid;
mso-list-template-ids:-1647802860 1944593008 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l2:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:\F0D8;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:"Times New Roman";}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l3
{mso-list-id:1826235738;
mso-list-template-ids:1090048536;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l3:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level4
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level5
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level7
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level8
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l4
{mso-list-id:1860927196;
mso-list-type:hybrid;
mso-list-template-ids:686343770 134807567 134807577 134807579 134807567 134807577 134807579 134807567 134807577 134807579;}
@list l4:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l4:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l4:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l4:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-GB link=blue vlink=purple><div class=WordSection1><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>I’m not familiar with PNaCl but, FWIW, I’d say the three main advancements the CLR made over the JVM are:<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText style='margin-left:36.0pt;text-indent:-18.0pt;mso-list:l1 level1 lfo1'><![if !supportLists]><span style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]>Structs (aka value types).<o:p></o:p></p><p class=MsoPlainText style='margin-left:36.0pt;text-indent:-18.0pt;mso-list:l1 level1 lfo1'><![if !supportLists]><span style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]>Reified generics. <a href="http://research.microsoft.com/pubs/64031/designandimplementationofgenerics.pdf">http://research.microsoft.com/pubs/64031/designandimplementationofgenerics.pdf</a><o:p></o:p></p><p class=MsoPlainText style='margin-left:36.0pt;text-indent:-18.0pt;mso-list:l1 level1 lfo1'><![if !supportLists]><span style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]>Tail call elimination. <a href="http://research.microsoft.com/pubs/69132/babel01.pdf">http://research.microsoft.com/pubs/69132/babel01.pdf</a><o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Structs give you more freedom around memory representation (e.g. the CLR can represent an array of pairs of floats and ints in a single contiguous block of memory whereas the JVM cannot). The main practical benefit is performance but also interoperability (e.g. SOA vs AOS with GPUs). In particular, as structs are (usually) unboxed they do not incur allocations, introduce indirections via pointers and do not stress the garbage collector. In fact, structs can be used to completely avoid the garbage collector’s contribution to latency (Rapid Addition used this technique to eliminate GC latency from their commercial FIX implementation <a href="http://www.microsoft.com/en-us/download/details.aspx?id=20918">http://www.microsoft.com/en-us/download/details.aspx?id=20918</a>). >From an implementation perspective, supporting structs makes it possible to get away with a much less efficient garbage collector because programmers can simply avoid the GC when necessary.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Reified generics combined with structs make it possible to write very efficient generic collections (e.g. .NET Dictionary can be 17x faster than Java’s HashTable because it is stored as a single continuous block of memory with no pointers <a href="http://fsharpnews.blogspot.co.uk/2010/05/java-vs-f.html">http://fsharpnews.blogspot.co.uk/2010/05/java-vs-f.html</a>).<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Tail call elimination allows an unbounded number of recursive function calls in tail position to consume finite stack space. This is essential for traditional functional programming but has other practical applications including representing state machines as mutually tail recursive functions and optimizing async code to avoid trampolines. F# relies upon the tail calls built into .NET since 2001. Note that tail call elimination applies not only to static function calls but also dynamic calls and it is an optimization in space and not time (on .NET general tail calls are ~2x <i>slower</i> than non-tail calls).<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Cheers,<o:p></o:p></p><p class=MsoPlainText>Jon.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText><span lang=EN-US style='mso-fareast-language:EN-GB'>-----Original Message-----<br>From: Travis Cross [mailto:tc@travislists.com] <br>Sent: 01 August 2013 07:55<br>To: Eli Bendersky<br>Cc: llvmdev@cs.uiuc.edu; Arnold Schwaighofer; Stephen Lin; Akira Hatanaka; Evan Cheng; Chris Lattner; Dale Johannesen; Duncan Sands; Jeffrey Yasskin; Jon Harrop; David Terei<br>Subject: Re: [LLVMdev] Tail calls (TCO) in PNaCL | PNaCl Bitcode reference manual</span></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>On 2013-07-30 22:11, Eli Bendersky wrote:<o:p></o:p></p><p class=MsoPlainText>> we've published an initial version of the PNaCl bitcode reference <o:p></o:p></p><p class=MsoPlainText>> manual online - <o:p></o:p></p><p class=MsoPlainText>> <a href="http://www.chromium.org/nativeclient/pnacl/bitcode-abi"><span style='color:windowtext;text-decoration:none'>http://www.chromium.org/nativeclient/pnacl/bitcode-abi</span></a>. The PNaCl <o:p></o:p></p><p class=MsoPlainText>> bitcode is a restricted subset of LLVM IR.<o:p></o:p></p><p class=MsoPlainText>> <o:p></o:p></p><p class=MsoPlainText>> Any comments would be most welcome.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Hi Eli,<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>I appreciate you for opening the process for input and comments. One question stood out to me while reading the document:<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>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.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Do I understand correctly that this means that reliable tail call optimization will not be possible under PNaCL as currently imagined?<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>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.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>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.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>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.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>If my understanding above is correct, how can we get PNaCL to support a sufficiently general calling convention to make TCO possible?<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>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?<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>I've CCed some individuals who might be interested in working out a solution here.<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>Thanks,<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>-- TC<o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>[1] <a href="http://www.chromium.org/nativeclient/pnacl/bitcode-abi"><span style='color:windowtext;text-decoration:none'>http://www.chromium.org/nativeclient/pnacl/bitcode-abi</span></a><o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>[2] <a href="http://llvm.org/releases/3.3/docs/LangRef.html#callingconv"><span style='color:windowtext;text-decoration:none'>http://llvm.org/releases/3.3/docs/LangRef.html#callingconv</span></a><o:p></o:p></p><p class=MsoPlainText><o:p> </o:p></p><p class=MsoPlainText>[3] <a href="https://sites.google.com/a/chromium.org/dev/nativeclient/pnacl/stability-of-the-pnacl-bitcode-abi"><span style='color:windowtext;text-decoration:none'>https://sites.google.com/a/chromium.org/dev/nativeclient/pnacl/stability-of-the-pnacl-bitcode-abi</span></a><o:p></o:p></p></div></body></html>