[llvm-dev] Improved jump-threading in LLVM for finite state automata

[Paweł Bylica via llvm-dev]

On Wed, Sep 23, 2020 at 9:48 PM Philip Reames via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

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

I believe the Wasm3 project (https://github.com/wasm3/wasm3) which is a
WebAssembly interpreter is using this dispatch technique described by
Philip.
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.

// Paweł


> 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.
>
> This is all thought experiment from my side; I haven't had time to sit
> down and actually prototype any of this.
>
> Philip
> On 9/23/20 7:33 AM, Phipps, Alan via llvm-dev wrote:
>
> 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:
>
>
>
> https://bugs.llvm.org/show_bug.cgi?id=42313
>
>
>
> It appears that GCC improved support for jump threading in 2015 along the
> same lines:
>
>
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54742
>
>
>
> Is anyone aware of any plan to do improve LLVM jump-threading along the
> same lines for LLVM?
>
>
>
> Thanks!
>
>
>
> Alan Phipps
>
>
>
> _______________________________________________
> LLVM Developers mailing listllvm-dev at lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200929/527e1acf/attachment.html>