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

[Philip Reames via llvm-dev]

On 9/29/20 3:39 AM, Paweł Bylica wrote:
> On Wed, Sep 23, 2020 at 9:48 PM Philip Reames via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto: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.
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).
>
> // 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 list
>>     llvm-dev at lists.llvm.org  <mailto:llvm-dev at lists.llvm.org>
>>     https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto: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/c8494706/attachment.html>