llvm dev - Sep 2020 - Improved jump-threading in LLVM for finite state automata

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200923/f0560703/attachment.html>

Nobody is currently working on this, as far as I know.  If you're interested
in looking into it, I'll try to answer any questions.

-Eli

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Phipps,
Alan via llvm-dev
Sent: Wednesday, September 23, 2020 7:34 AM
To: llvm-dev at lists.llvm.org
Subject: [EXT] [llvm-dev] Improved jump-threading in LLVM for finite state
automata

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200923/0f20974b/attachment.html>

+ Evgeny

We have a jump threading pass downstream for this that we would love to
upstream. I believe Evgeny was working on exactly this, i.e. preparing it for
upstreaming.

________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Eli
Friedman via llvm-dev <llvm-dev at lists.llvm.org>
Sent: 23 September 2020 19:16
To: Phipps, Alan <a-phipps at ti.com>; llvm-dev at lists.llvm.org
<llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Improved jump-threading in LLVM for finite state
automata


Nobody is currently working on this, as far as I know.  If you’re interested in
looking into it, I’ll try to answer any questions.



-Eli



From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Phipps,
Alan via llvm-dev
Sent: Wednesday, September 23, 2020 7:34 AM
To: llvm-dev at lists.llvm.org
Subject: [EXT] [llvm-dev] Improved jump-threading in LLVM for finite state
automata



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


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200923/9bc8b75c/attachment.html>

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'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 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/20200923/a5664191/attachment.html>

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>