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

[Philip Reames via llvm-dev]

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>