<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 9/29/20 3:39 AM, Paweł Bylica wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAE7VtSerf-qWyrttp8UEN9O5Ddz161SB-iLM=Vk5jiS12zYCHg@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Sep 23, 2020 at 9:48
PM Philip Reames via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div>
<p>No active work on my side, but I have given the topic
of threaded interpreters (which is what I think you're
wanting to produce) a good amount of thought. <br>
</p>
<p>I'm really not sure that switch is the right canonical
form. The main reason being that having a loop over a
large switch is very likely to encourage code motion
which is generally profitable, but harmful in this
particular context.</p>
<p>I had been thinking down the lines of representing the
intepreter as a family of mutually recursive functions
with a calling convention optimized for this case and
using a musttail call through a lookup table for the
dispatch. </p>
</div>
</blockquote>
<div><br>
</div>
<div>I believe the Wasm3 project (<a
href="https://github.com/wasm3/wasm3"
moz-do-not-send="true">https://github.com/wasm3/wasm3</a>)
which is a WebAssembly interpreter is using this dispatch
technique described by Philip.</div>
<div>I don't know how exactly it is guaranteed that the
indirect calls are converted to tail calls (maybe it's not).
But the performance is quite impressive.</div>
</div>
</div>
</blockquote>
Interesting, I hadn't seen this. Reading through the docs, it looks
like M3 (the wasm3 interpreter) isn't able to guarantee tail call
dispatch which isn't surprising. There's a whole section on
managing stack space with some special tricks around loops. I will
note there's at least one key misstatement in the description.
Branches do not fundamentally need stack space. Calls do - as
correctly noted. Still cool to see someone playing with this in
modern times, most of the usage I'm familiar with is in older papers
(e.g. the threaded code context referenced at the bottom of the M3
description).<br>
<blockquote type="cite"
cite="mid:CAE7VtSerf-qWyrttp8UEN9O5Ddz161SB-iLM=Vk5jiS12zYCHg@mail.gmail.com">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>// Paweł<br>
</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div>
<p>I've played with the notion of extending clang with a
custom attribute for guaranteed tail calls. I think
this is pretty much the only extension needed to be able
to natively write out a threaded interpreter as a set of
mutually recursive functions.</p>
<p>This is all thought experiment from my side; I haven't
had time to sit down and actually prototype any of this.</p>
<p>Philip<br>
</p>
<div>On 9/23/20 7:33 AM, Phipps, Alan via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div>
<p class="MsoNormal">It is my understanding that the
implementation for jump-threading in LLVM is not
presently able to effectively optimize code
containing a state-machine implemented using a loop
+ switch. This is the case, for example, with the
Coremark benchmark function
core_state_transition(). Bug 42313 was filed to
address this in 2019:</p>
<p class="MsoNormal"> </p>
<p class="MsoNormal"><a
href="https://bugs.llvm.org/show_bug.cgi?id=42313"
target="_blank" moz-do-not-send="true">https://bugs.llvm.org/show_bug.cgi?id=42313</a></p>
<p class="MsoNormal"> </p>
<p class="MsoNormal">It appears that GCC improved
support for jump threading in 2015 along the same
lines:</p>
<p class="MsoNormal"> </p>
<p class="MsoNormal"><a
href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54742"
target="_blank" moz-do-not-send="true">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54742</a></p>
<p class="MsoNormal"> </p>
<p class="MsoNormal">Is anyone aware of any plan to do
improve LLVM jump-threading along the same lines for
LLVM?</p>
<p class="MsoNormal"> </p>
<p class="MsoNormal">Thanks!</p>
<p class="MsoNormal"> </p>
<p class="MsoNormal">Alan Phipps</p>
<p class="MsoNormal"> </p>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" moz-do-not-send="true">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</div>
</blockquote>
</body>
</html>