Re: Lightning Bindings
() Noah Lavine noah.b.lav...@gmail.com () Tue, 1 Jun 2010 10:57:15 -0400 I didn't realize GCC had a Lisp interface. It has a recently (2009?) approved run-time plug-in system, for which MELT is one example. Incidently, Emacs also has also recently won approval for the development of a analogous architecture, so... Interfacing with GCC would be excellent. ...yeah, i think the most riteous hack would involve GCC (and Emacs). That's not to say there could be other valid (and most likely easier to achieve with less work) approaches. This is perhaps far-fetched, but I think the best thing would be if we could persuade them to replace MELT with Guile. It looks to me from the docs like MELT is yet another Lisp engine, which is exactly what Guile is trying to replace. We could offer them a well-tested, more-feature-complete extension language, and they could offer us interfaces to good code generation. On this i disagree, perhaps because persuasion is not one of my strengths. I tend to think, what if i were the MELT hacker? Would i want this kind of noise in my playground? My answer might well be: Why don't you study MELT, develop a congruent Guile-based system, and then we'll talk. But that's just the curmudgeon (who perceives precious time passing ever faster) in me talking; take it FWIW. I hope you keep us updated on this matter -- it's very exciting in any case! thi
Re: Lightning Bindings
Hi Noah, On Thu 27 May 2010 23:03, Noah Lavine noah.b.lav...@gmail.com writes: I now have a start at working bindings for Lightning, which you can see at http://github.com/noahl/guile-lightning. Fascinating! Congrats on getting through the foreign function docs; a high-level interface is really necessary there... But very cool to see that you were able to get something working with so little code! - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Second question first :) I collected my general thoughts on native code compilation here: http://thread.gmane.org/gmane.lisp.guile.devel/10234 I feel quite strongly that the calling convention for native code should be the same as that of bytecode, and that it should use the same stack. This way we don't have to maintain separate stack walkers or debuggers or the like. Also this way we get proper tail calls and multiple value handling as well. I tend to think that Ludovic's proposal, or something like it, is the most practical means to get a portable JIT compiler going; though I don't really know. In the end though Guile needs to be generating native code ahead-of-time, I think. Doing that portably is hard; we'll need to leverage some other project. I think that project should be GCC. I was talking to Dodji Seketeli the other day, a GCC dev, and he says that GCC maintainers are willing to allow other programs to use it for code generation, but they don't know yet what abstractions they need to provide. So first we should probably implement a native code compiler directly ourselves, for one architecture, and see how that experience changes our internal language barriers and then go to GCC with a set of requirements. (Since I know the question will come up, possibilities are numerous -- basically we want to emit something on the RTL level, I think, though I'm sure there will be much back-and-forth here; and licensing-wise, it might involve a build server (already planned), or a plugin, or a library. It will take a couple years I think.) - First, would you like Lightning bindings? As I said, I think it's the fastest way to get some native code generation going, but I don't think it'll ultimately be the best. At the very least it's an interesting tool to have! Though I do agree though that it's not ideal. (I can clean up and post my notes on different code generation systems if you'd like them.) I would be very interested in your observations, yes :) Thank you Noah Lavine Thank you! Andy -- http://wingolog.org/
Re: Lightning Bindings
Hi Noah, On Tue 01 Jun 2010 00:49, Noah Lavine noah...@gmail.com writes: The approach in [Ludovic's] plan for JIT, as I understand it, is to implement this completely in the C layer. The machine code would be stored as part of the representation of a procedure, and would be invisible from the Scheme side. Well, one should always be able to disassemble that code, architectures permitting :) I do think this is the right way to go FWIW, though perhaps we should only JIT existing procedures after they have been called some number of times. There is also the Rubinius strategy of offloading JIT compilation to a separate thread, but that shouldn't be necessary... As for doing it all in C, I am concerned about this because if there were bindings available in Scheme, then it might be possible to write a nice compiler in Scheme someday, which would do clever things like inlining and interprocedural optimization. I think we'll have this eventually, yes -- but that's at a level above native code generation. This kind of optimization is best done as source-to-source transformations of Tree-IL, IMO. See e.g. Oscar Waddell's thesis. What do you think of this? What way should I try to implement this? Are you most interested in AOT compilation or JIT compilation? If it's JIT, I would work on something more like Ludovic's solution; if it's AOT compilation, I would see about making a compiler from one of Guile's intermediat languages to a new lightning language. See Compiler Tower in the manual. Just my opinion anyway :) Cheers, Andy -- http://wingolog.org/
Re: Lightning Bindings
On Tue, Jun 1, 2010 at 5:06 AM, Andy Wingo wi...@pobox.com wrote: Hi Noah, Hi Andy! I feel quite strongly that the calling convention for native code should be the same as that of bytecode, and that it should use the same stack. This way we don't have to maintain separate stack walkers or debuggers or the like. Also this way we get proper tail calls and multiple value handling as well. That makes a lot of sense. I tend to think that Ludovic's proposal, or something like it, is the most practical means to get a portable JIT compiler going; though I don't really know. You may be right; although I think actually with the FFI, it would be just as easy to get it going in Scheme. According to the docs, right now Scheme code can access any function in the Guile binary - including the functions that implement the VM instructions. I was planning to just use that capability to generate machine code that called those C functions. I just thought of another thing that would be good to think about. I think we might ultimately not want to be generating machine code for each procedure, because that would make it impossible to do tracing optimizations like current JavaScript engines (if I understand the proposal right), and also because that might lead to generating a lot of machine code for non-bottleneck points just to get at one bottleneck. I don't think this is something we should try to implement now, but it'd be nice if the code generation infrastructure was flexible enough that it could be added on later. That also raises another point I had forgotten about. Your earlier thread asked how to get native code generation for Guile in such a way that it didn't make Guile too big to understand. I think a good choice would be to *not* put code generation in the core of Guile. Instead, make a module you can load that will generate native code. Maybe it would offer an alternate language, compiled-guile, or something. It doesn't even have to be distributed with the Guile libraries, although it probably would be. This has two advantages - first, it makes core Guile small. Perhaps people who do embedded systems would appreciate that, or who want to embed Guile in their programs and care more about small code size than incredible speed. Second, it gives you the chance to have multiple native code backends at once. For instance, a JIT and an AOT backend. All you really need for this is a way for core Guile to call native code, which you now have with the FFI. In the end though Guile needs to be generating native code ahead-of-time, I think. Doing that portably is hard; we'll need to leverage some other project. I think that project should be GCC. I was talking to Dodji Seketeli the other day, a GCC dev, and he says that GCC maintainers are willing to allow other programs to use it for code generation, but they don't know yet what abstractions they need to provide. Oh, that's excellent! When I was looking at options earlier, I thought that GCC would be the ideal, but it would be too hard to use their stuff. If they're willing to work on this, then probably that would be best. I would be very interested in your observations, yes :) Well, here are some thoughts on existing work that we might be able to reuse: Nanojit - from Mozilla and Adobe. C++ library for code generation. Has optional optimization passes, but could be used without them. Probably good, but extremely poorly documented. SpiderMonkey - the JavaScript runtime from Firefox, written in C++. In order to be useful, you'd probably have to take out most of their primitive operations and replace them with your own. You'd also have to understand their garbage collection and figure out how it interfaced with Guile's. The upside would be potentially extremely fast code generation, since you'd get the tracing JIT and the fast native code generation. The downside would be a lot of complexity. Has an LGPL license (among others). GNU Lightning - a very simple native code generator, written in C. The upside would be its extreme simplicity. The downside would be the apparently total lack of optimization. GCC - the ideal. It has the best AOT compilation of everything listed here, but it'd need work to use it. I think the biggest obstacle is that GCC assumes everything is written to and from a file. You'd need to change that to use it as a JIT backend. (The biggest issue is that the compiler and assembler are only connected through files.) Other than that, though, it shouldn't be too bad to wrap its C interfaces with the FFI. (Possible idea: get the GCC developers working with us by offering to replace GCC MELT with Guile if they'll make nicer backend interfaces. Everyone would win.) PLT Scheme - contains MzScheme, an LGPL-licensed Scheme interpreter with a JIT backend. Their backend is just a hacked version of Lightning, so it might not be much faster than what we would have with our own Lightning backend,
Re: Lightning Bindings
I didn't realize GCC had a Lisp interface. Interfacing with GCC would be excellent. This is perhaps far-fetched, but I think the best thing would be if we could persuade them to replace MELT with Guile. It looks to me from the docs like MELT is yet another Lisp engine, which is exactly what Guile is trying to replace. We could offer them a well-tested, more-feature-complete extension language, and they could offer us interfaces to good code generation. Noah On Sat, May 29, 2010 at 4:09 PM, Thien-Thi Nguyen t...@gnuvola.org wrote: () Noah Lavine noah.b.lav...@gmail.com () Thu, 27 May 2010 17:03:48 -0400 - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Perhaps you can look at how MELT (for GCC) does things. Keeping within striking distance of GCC interop (i.e., its plugin design) is probably a lot of work, but maybe the benefit would be greater. thi
Re: Lightning Bindings
Hello, Noah Lavine noah.b.lav...@gmail.com writes: I didn't realize GCC had a Lisp interface. Interfacing with GCC would be excellent. MELT is a “middle end”, useful when writing optimization passes, but not when writing a front-end. This is perhaps far-fetched, but I think the best thing would be if we could persuade them to replace MELT with Guile. It looks to me from the docs like MELT is yet another Lisp engine, which is exactly what Guile is trying to replace. We could offer them a well-tested, more-feature-complete extension language, and they could offer us interfaces to good code generation. I don’t think that’d work because MELT is very tightly integrated with GCC’s internals AIUI. Thanks, Ludo’.
Re: Lightning Bindings
Hi Noah! Noah Lavine noah...@gmail.com writes: Here is my understanding of the three approaches: The approach in my project was to make machine code a Guile datatype, which you could allocate with a special init function and write to with writing functions which are just Guile versions of the Lightning macros. It could be called as a function through the dynamic FFI. The approach in the other guile-lightning project is to represent the Lightning code as a Guile list which mirrors the Lightning virtual instruction set. When a list is completely built, it would then be passed to a special function (written in C) to assemble it. It also has some infrastructure for labels and a special method of calling these functions, neither of which I understand yet. The approach in your plan for JIT, as I understand it, is to implement this completely in the C layer. The machine code would be stored as part of the representation of a procedure, and would be invisible from the Scheme side. Yes. The reason I did not use the approach of the other guile-lightning, to make a list and then assemble it, was that it seemed inelegant and possibly slow It depends on when and how the instruction stream is written. From a usability viewpoint, having a simple s-exp for asm instructions is nice (and elegant, IMO). OTOH, I find the ‘make-integer-id’ example at http://github.com/noahl/guile-lightning/blob/master/binds.scm quite elegant too. BTW, note that end-of-buffer situations must be handled, somehow. If the whole call generation procedure is burried in a single C functions, it can hide these details to the application. Otherwise, it’d be up to the application to handle this situation, e.g., by linking two code buffers together and adding a jump instruction in the first one to the second one. Anyway, these are just random thoughts. Thanks, Ludo’.
Re: Lightning Bindings
They claim that MELT is tightly integrated with GCC, but after reading http://gcc.gnu.org/wiki/MiddleEndLispTranslator, I don't believe it. The MELT compiler implementation description suggests that it's a pretty simple-minded sexp-to-C translator. I also notice that none of the examples has any control structures more complicated than `if` and `foreach`. I'd say it's basically a nice syntax for messing with GCC data structures. When the page says very tightly integrated into GCC, it seems to mean has boxed versions of a few internal GCC data structures (there's a list on the page I link. It's not very long). That shouldn't be hard at all to connect Guile to. The only part that could be tricky is interfacing with GCC's garbage collection. I don't know how Guile's FFI interacts with other memory management systems, so this could be a problem, but I think it could be done. It's going to have to be solved anyway if Guile is going to interface with other memory management systems. Besides, this is one of Guile's objectives, isn't it? GNU programs shouldn't need to implement their own extension languages, because Guile can handle it. Noah
Re: Lightning Bindings
Hi Ludo, I didn't realize guile-lightning existed! It looks like that project already has most of the code for Lightning bindings, so it might be better to try to update it to work with Guile 2.0. I also saw your idea for JIT, which I could work on as well. However, all three projects use different ideas of how Lightning should connect to Guile, so before I code more I would like to talk about which would be better. Here is my understanding of the three approaches: The approach in my project was to make machine code a Guile datatype, which you could allocate with a special init function and write to with writing functions which are just Guile versions of the Lightning macros. It could be called as a function through the dynamic FFI. The approach in the other guile-lightning project is to represent the Lightning code as a Guile list which mirrors the Lightning virtual instruction set. When a list is completely built, it would then be passed to a special function (written in C) to assemble it. It also has some infrastructure for labels and a special method of calling these functions, neither of which I understand yet. The approach in your plan for JIT, as I understand it, is to implement this completely in the C layer. The machine code would be stored as part of the representation of a procedure, and would be invisible from the Scheme side. (I should also point out that my plan for compilation was to first start generating machine code with as few inlined instructions as possible, which would just call VM functions to do its work. This was also your plan, and I believe also the plan of the earlier guile-lightning project.) It is not clear to me which one of these is the best way, or even if there is a best way. The reason I did not use the approach of the other guile-lightning, to make a list and then assemble it, was that it seemed inelegant and possibly slow to have to iterate through instructions twice whenever I compiled something, first to generate the list and then to compile it. However, I doubt it would be very slow, and thinking about it now it might even be faster if the iteration programs became smaller and fit in cache. As for doing it all in C, I am concerned about this because if there were bindings available in Scheme, then it might be possible to write a nice compiler in Scheme someday, which would do clever things like inlining and interprocedural optimization. (Or, more easily, persuade the MIT Scheme or Bigloo people to donate their compilers.) Writing it in C could make that more difficult - but if it also made Guile programs faster right now, then it might be worth doing anyway. What do you think of this? What way should I try to implement this? Noah
Re: Lightning Bindings
() Noah Lavine noah.b.lav...@gmail.com () Thu, 27 May 2010 17:03:48 -0400 - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Perhaps you can look at how MELT (for GCC) does things. Keeping within striking distance of GCC interop (i.e., its plugin design) is probably a lot of work, but maybe the benefit would be greater. thi
Re: Lightning Bindings
Hi Noah, Noah Lavine noah.b.lav...@gmail.com writes: After watching the discussion of native code generation on this list a few weeks ago, I decided I'd like to help. I looked at several possibilities, but it seemed like the easiest and most sure way of making *something* work was writing bindings to GNU Lightning. Excellent! Have you looked at, ahem, guile-lightning? :-) http://cvs.savannah.gnu.org/viewvc/guile/guile-lightning/?root=guile As you can see it’s an old attempt to do this. I haven’t looked in detail, but there may be ideas or code to borrow. My thought was to do enough of the Lightning API that it could call C functions, and then implement a compiler from Guile VM code to native Lightning-generated code that just called a series of VM functions. There wouldn't be any inlining or cool things like that, but it would be a start. You could then add inlining support for individual VM functions as it seemed important. I had a vague plan to implement JIT in the VM using lightning in C: http://www.fdn.fr/~lcourtes/software/guile/jit.html The (presumed) advantage is that opcodes from vm-*.c could be largely reused. The obvious disadvantage is that it would be C. Writing lightning assembly can be tedious, but probably less so if done in Scheme. - First, would you like Lightning bindings? Yes! :-) - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Something close to lightning at the lowest level probably makes sense. Then there could be a higher-level interface like http://cvs.savannah.gnu.org/viewvc/guile/guile-lightning/compiler.scm?revision=1.3root=guileview=markup or close to the VM’s own assembly. Looking at http://github.com/noahl/guile-lightning/blob/master/binds.scm it seems that you plan to have one subr for each lightning instruction. That would make the cost of assembling a single instruction quite high, compared to that of the raw lightning C macros. Thanks, Ludo’.
Re: Lightning Bindings
Neat! Have you looked into libjit? The only reason I bring it up is because it seems to be more popular than Lightning and already has some third-party language bindings. On Thu, May 27, 2010 at 4:03 PM, Noah Lavine noah.b.lav...@gmail.com wrote: Dear Guile Developers, After watching the discussion of native code generation on this list a few weeks ago, I decided I'd like to help. I looked at several possibilities, but it seemed like the easiest and most sure way of making *something* work was writing bindings to GNU Lightning. I now have a start at working bindings for Lightning, which you can see at http://github.com/noahl/guile-lightning. Currently it can only use a few Lightning instructions, but I have enough to verify that it generates executable code and that code interfaces with Guile. At this point I could fairly easily go through the Lightning manual and add more functions, command-by-command, until I had a complete interface to the Lightning API. My thought was to do enough of the Lightning API that it could call C functions, and then implement a compiler from Guile VM code to native Lightning-generated code that just called a series of VM functions. There wouldn't be any inlining or cool things like that, but it would be a start. You could then add inlining support for individual VM functions as it seemed important. At that point I would also want to wrap the rest of the Lightning API, both so that inlined VM functions could use it and so that other Guile programs could use Lightning like any other module. However, I would like to ask two questions before I do that, to make sure the result is ultimately useful. - First, would you like Lightning bindings? As I said, I think it's the fastest way to get some native code generation going, but I don't think it'll ultimately be the best. (I can clean up and post my notes on different code generation systems if you'd like them.) - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Thank you Noah Lavine
Re: Lightning Bindings
Yes, I tried, but I couldn't get it to build on my system for some reason, so I went with Lightning. I could try harder to get it to build if it seems like a good choice. On Fri, May 28, 2010 at 4:49 PM, No Itisnt theseaisinh...@gmail.com wrote: Neat! Have you looked into libjit? The only reason I bring it up is because it seems to be more popular than Lightning and already has some third-party language bindings. On Thu, May 27, 2010 at 4:03 PM, Noah Lavine noah.b.lav...@gmail.com wrote: Dear Guile Developers, After watching the discussion of native code generation on this list a few weeks ago, I decided I'd like to help. I looked at several possibilities, but it seemed like the easiest and most sure way of making *something* work was writing bindings to GNU Lightning. I now have a start at working bindings for Lightning, which you can see at http://github.com/noahl/guile-lightning. Currently it can only use a few Lightning instructions, but I have enough to verify that it generates executable code and that code interfaces with Guile. At this point I could fairly easily go through the Lightning manual and add more functions, command-by-command, until I had a complete interface to the Lightning API. My thought was to do enough of the Lightning API that it could call C functions, and then implement a compiler from Guile VM code to native Lightning-generated code that just called a series of VM functions. There wouldn't be any inlining or cool things like that, but it would be a start. You could then add inlining support for individual VM functions as it seemed important. At that point I would also want to wrap the rest of the Lightning API, both so that inlined VM functions could use it and so that other Guile programs could use Lightning like any other module. However, I would like to ask two questions before I do that, to make sure the result is ultimately useful. - First, would you like Lightning bindings? As I said, I think it's the fastest way to get some native code generation going, but I don't think it'll ultimately be the best. (I can clean up and post my notes on different code generation systems if you'd like them.) - Second, what would a good interface to a native code generation system be? (I'm assuming we'll want Lightning available as a regular module in addition to using it to speed up the language.) My current prototype just mimics the Lightning API, but it's not necessarily the best way to do this. Is there a better way? Thank you Noah Lavine
