Phipps, Alan via llvm-dev
2020-Sep-23 14:33 UTC
[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/f0560703/attachment.html>
Eli Friedman via llvm-dev
2020-Sep-23 18:16 UTC
[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/0f20974b/attachment.html>
Sjoerd Meijer via llvm-dev
2020-Sep-23 19:03 UTC
[llvm-dev] Improved jump-threading in LLVM for finite state automata
+ 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>
Philip Reames via llvm-dev
2020-Sep-23 19:47 UTC
[llvm-dev] Improved jump-threading in LLVM for finite state automata
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>
Paweł Bylica via llvm-dev
2020-Sep-29 10:39 UTC
[llvm-dev] Improved jump-threading in LLVM for finite state automata
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>