Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Dec 5, 2010, at 23:34 , Erik de Castro Lopo wrote: Benedikt Meurer wrote: Using a different data representation within OCaml would indeed be possible, but one has to ask what it's worth? Is it necessary to use a different data representation? What does that buy you? Read my mail again please, it was all about the data representation issues. the standard library and the bytecode interpreter (already a massive amount of work), Why? Because you want to keep the bytecode interpreter in sync, otherwise you can no longer share any piece of C code between ocamlopt and ocaml/ocamlrun. but you also loose compatibility with almost every existing OCaml library binding, since the native function interface will be different. That's a hell of a lot of work for many people. Again, why? When the GHC haskell compiler gained an LLVM backend, the LLVM project accepted changes to allow a new GHC specific calling convention. Couldn't the same be done for Ocaml? This is not about calling conventions, and also not about LLVM. This is about data representation. 3. The current garbage collector is mostly straight-forward because of There is no need to use LLVM's GC if something better already exists. LLVM does not provide a GC. Two main areas for now: The GC interface and the exception handling. If the Ocaml versions of these are already better than what LLVM can provide, here is no reason to use the LLVM versions. It isn't as simple. With LLVM you are no longer in control of the code generation. The ocaml versions use special registers and stack layout, which will not work with LLVM's code generation unless LLVM is patched appropriately. Erik Benedikt ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Sun, Dec 05, 2010 at 05:37:32PM +0100, Benedikt Meurer wrote: 1. You will have to rewrite not only the compiler, the standard library and the bytecode interpreter (already a massive amount of work), but you also loose compatibility with almost every existing OCaml library binding, since the native function interface will be different. That's a hell of a lot of work for many people. It might kick-start efforts to automatically generate bindings, at least to C code, which wouldn't be a bad thing. camlidl is clumsy and doesn't handle a very important case (pointers to handles) so it's not really useful for this. I do agree with the rest of your points though, and it's good to have intelligent discussion of the real issues at long last. Rich. -- Richard Jones Red Hat ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
RE: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
Richard Jones wrote: It might kick-start efforts to automatically generate bindings, at least to C code, which wouldn't be a bad thing. camlidl is clumsy and doesn't handle a very important case (pointers to handles) so it's not really useful for this. Yes, LLVM is ideal for this. Using LLVM to JIT compile OCaml-C interop stubs should be quite easy. I did a bit of this in some of the OCaml Journal article that were on LLVM. You could also kill two birds with one stone by creating an OCaml-HLVM bridge with it. That would make it easier to create a bigarray from OCaml and call into high-performance parallel numerical code to chomp on it. Cheers, Jon. ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Sun, 5 Dec 2010 17:37:32 +0100 Benedikt Meurer benedikt.meu...@googlemail.com wrote: Two main areas for now: The GC interface and the exception handling. LLVM's exception support is really limited; the GC support is better and more generic. I don't know how to implement the OCaml exception model within LLVM w/o adding a lot of special case stuff to LLVM itself (mentioned in my original post); if there would be a way to easily extend LLVM with special exception models, other projects could plug in their models. There is a discussion on the LLVM mailing list about changing exception handling in LLVM: http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-December/036692.html If the new model is not generic enough to support OCaml's model, then I think now would be a good time to describe on the LLVM ML what OCaml's model would need and the proposal doesn't cover. Best regards, --Edwin ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Dec 5, 2010, at 17:57 , Török Edwin wrote: On Sun, 5 Dec 2010 17:37:32 +0100 Benedikt Meurer benedikt.meu...@googlemail.com wrote: Two main areas for now: The GC interface and the exception handling. LLVM's exception support is really limited; the GC support is better and more generic. I don't know how to implement the OCaml exception model within LLVM w/o adding a lot of special case stuff to LLVM itself (mentioned in my original post); if there would be a way to easily extend LLVM with special exception models, other projects could plug in their models. There is a discussion on the LLVM mailing list about changing exception handling in LLVM: http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-December/036692.html If the new model is not generic enough to support OCaml's model, then I think now would be a good time to describe on the LLVM ML what OCaml's model would need and the proposal doesn't cover. It's not a different model, but a better implementation of what is already available. From what I've seen now, the best starting point seems to be the setjmp/longjmp model, which is supported by LLVM. It's certainly slower than the current scheme, but well, it would be a starting point. Best regards, --Edwin Benedikt ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Dec 5, 2010, at 21:12 , Jon Harrop wrote: Benedikt wrote: On Dec 3, 2010, at 21:07 , Jon Harrop wrote: Benedikt wrote: So, let's take that LLVM thing to a somewhat more serious level (which means no more arguing with toy projects that simply ignore the difficult stuff). You can learn a lot from prototypes. Indeed, but you need stay on topic. HLVM does not prototype the use of LLVM within OCaml, because you're using a quite different data representation. My point was that HLVM's data representation is far more flexible than ocamlopt's, so you can use it to measure the effect of changing data representations on the efficiency of the code LLVM generates more easily than with ocamlopt. In particular, I am saying that (from my own measurements) LLVM does not cope with data representations like ocamlopt's at all well. Specifically, when you box and cast away type information. My guess is that retargeting ocamlopt to LLVM IR (which is a considerable undertaking due to the amount of hacking required on LLVM itself) would result in more performance degradation that improvement. Moreover, that degradation is most likely to occur on code like Coq because ocamlopt has been so heavily optimized for that one application domain and, consequently, I doubt your hard work would ever be accepted into mainstream OCaml. Ultimately, LLVM was built specifically to exploit a typed intermediate representation whereas ocamlopt removes type information very early. From what I've seen so far, LLVM makes little use of the type information, especially integer and pointer types are treated nearly the same, so LLVM won't benefit from this information. Any other data is still distinguished at the Cmm level (i.e. doubles, strings, ...), which is necessary for the register allocation and instruction selection phase in ocamlopt. You could easily change the intermediate representations in ocaml (lambda, ulambda, cmm) to include additional type information, so this is not the problem. But as said, it won't help a lot with LLVM. Also looking at the GHC work you mentioned, they also start at the Cmm level (slightly different C--, but comparable to ocamlopt), with mostly the same amount of type information available. And as you said, they did quite well in some cases. Using a different data representation within OCaml would indeed be possible, but one has to ask what it's worth? You'd get better floating point performance (most likely) And faster tuples, ints, chars, complex numbers, low-dimensional vectors/matrices, hash tables and so on. More types (e.g. int16 and float32). Even arbitrary-precision arithmetic can benefit by keeping small numbers unboxed when possible. Bigarrays disappear. The FFI gets simpler, easier to use and more powerful (e.g. you can generate AoS layouts for OpenGL). The benefits are enormous in the general case but that is beside the point here. Moreover, this would never be accepted either because it would degrade the performance of applications like Coq. If it is done at all, such work must be kept separate from the OCaml compilers. ocamlopt already supports float32 and int16, tho they are not exploited to the upper layers (don't know why, but I also don't know why one would need them). Keeping Int32/Int64 values unboxed would be possible similar to what is done with doubles; maybe there is simply no need to do (honestly, I've never needed Int32/Int64 so far, int/Natint is usually what you want and these are optimized). 3. The current garbage collector is mostly straight-forward because of the data representation. No need to carry around/load type information, Note that conveying run-time type information also facilitates useful features like generic printing. Generic printing is currently implemented using the run-time type information (the three bits mentioned below). you just need the following bits of information: Is it a block in the heap? Does it contain pointers? If so how many? All this information is immediately available with the current data representation (also improves cache locality of the GC loops). That information is also immediately available with HLVM's design. Each value contains a pointer to its run-time type. Each run-time type contains a pointer to a visit function for the GC that returns the references in any value of that type. This is indeed possible, yes, and also implemented by most Java VMs; each objects ships a type-info pointer. OCaml avoids the type-info pointer using clever header field encoding. A matter of taste probably. So, it is really worth to spend years on a new data representation (including fixing all C bindings, etc.)? Just to get better floating point performance? Integer performance will be almost the same, avoiding the shift/tag bit just replaces an addq r1, r2; subq $1, r2 with addq r1, r2; even doing this thousands of times will not cause a noticeable difference. On
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Dec 5, 2010, at 22:21 , Benedikt Meurer wrote: On Dec 5, 2010, at 21:12 , Jon Harrop wrote: Using a different data representation within OCaml would indeed be possible, but one has to ask what it's worth? You'd get better floating point performance (most likely) And faster tuples, ints, chars, complex numbers, low-dimensional vectors/matrices, hash tables and so on. More types (e.g. int16 and float32). Even arbitrary-precision arithmetic can benefit by keeping small numbers unboxed when possible. Bigarrays disappear. The FFI gets simpler, easier to use and more powerful (e.g. you can generate AoS layouts for OpenGL). The benefits are enormous in the general case but that is beside the point here. Moreover, this would never be accepted either because it would degrade the performance of applications like Coq. If it is done at all, such work must be kept separate from the OCaml compilers. ocamlopt already supports float32 and int16, tho they are not exploited to the upper layers (don't know why, but I also don't know why one would need them). To be exact, you could load/store float32 and int16 values. At least for int16, computations would be less efficient on modern CPUs, since the partial register reads/writes would create false dependencies and therefore result in less efficient instruction scheduling (similar for float32 with SSE2, i.e. divss leaves the three higher doublewords of the target register unchanged, thereby introducing false dependencies on previous instructions). Benedikt ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
Is there IPA in LLVM? I didn't know that. -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On Fri, 3 Dec 2010 15:41:41 +0200 Eray Ozkural examach...@gmail.com wrote: Is there IPA in LLVM? I didn't know that. See createStandardLTOPasses and the UnitAtATime part of createStandardModulePasses: http://llvm.org/svn/llvm-project/llvm/trunk/include/llvm/Support/StandardPasses.h Also http://llvm.org/svn/llvm-project/llvm/trunk/include/llvm/Transforms/IPO.h http://llvm.org/svn/llvm-project/llvm/trunk/lib/Analysis/IPA I doubt they'll be able to figure out everything on their own though, the frontend should probably add some extra info. For example by adding some function attributes, or some metadata about the high-level types. I see that LLVM has a metadata based TBAA, but right now it is for C/C++, so I'm not sure it could take advantage of all the properties of a functional language. It'd probably be better if an OCamlAA was written (perhaps building on the already existing TBAA, or improving that) that takes advantage of immutable data structures and OCaml's type system. Best regards, --Edwin ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
I'm totally noob on compilers internals, but if the processing of float arrays can be improved a lot by a LLVM ocamlopt, I would use it exclusively. Le 3 déc. 2010 à 11:03, Benedikt Meurer a écrit : So, let's take that LLVM thing to a somewhat more serious level (which means no more arguing with toy projects that simply ignore the difficult stuff). What would be necessary to support LLVM in ocamlopt, and what would be the benefits? First, what has to be done: 1. Obviously, one would need to emit LLVM code from ocamlopt (starting at the Cmm level). Following the GHC/EHC approach we could simply emit the .ll file here as a starting point (no fiddling with the LLVM API then, could still switch to the LLVM API later for runtime code generation). 2. LLVM would need to generate the stack maps for the GC and the required symbols for the program (code_begin, code_end, data_begin, data_end). LLVM already contains an OcamlGCPrinter class, which seems to do exactly this; so this may be easy. 3a. If the current runtime is to be reused, LLVM will have to support OCaml calling conventions (easy to implement, did that already), LLVM must be taught about the OCaml runtime state (i.e. %r14 and %r15 on x86-64 must not be used by LLVM, also easy to implement), and LLVM must be extended with intrinsics to support allocation and exception handling with appropriate lowering for the targets (somewhat difficult and questionable whether this will be merged into LLVM, since it's usable by OCaml only). 3b. Alternatively we could also replace the native interface of the current runtime with something that fits better with what is already provided by LLVM (which isn't a lot, so we would have to limit ourselves somewhat). Allocation and GC are possible without too many changes here, but the exception handling is really difficult, since LLVM doesn't provide anything usable here; we'd either need to do everything by hand or use one of the two modes provided by LLVM (overhead, most probably). 4. We need a way to emit Cmm data items. LLVM cannot handle this ATM, which should be fixed (dunno how yet). In the meantime we can emit Cmm data items using module level asm. It is important to note that we won't get anything for free. Work is required for every single platform we plan to support using the LLVM backend. This is probably the case for every serious programming language (and no, we don't need another mention of HLVM here, it's a toy, that's all). So, there's some boring and probably some interesting work to be done, but what do we gain? 1. Reduce lines of code and improved maintainability of ocamlopt once all targets are replaced with the LLVM backend. But as said, this does itself come at a cost, and depending on whether 3a. or 3b. is implemented, we burden ourselves with maintaining code within LLVM. 2. Some interesting optimizations and all the standard optimizations for free. 3. A better LLVM. If we do it right, other's implementing functional languages using LLVM will not be faced with the same problems again. Dunno if that's possible. 4. And for the kids: LLVM is cool, OCaml will use LLVM, so OCaml is also cool. ;-) Anything I forgot to mention? Comments? Benedikt ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
On 12/03/2010 04:03 AM, Benedikt Meurer wrote: 2. Some interesting optimizations and all the standard optimizations for free. We would also get new optimizations developed by the compiler backend and computer architecture researchers working on LLVM for free. I see that as one of the major benefits - it lets the OCaml community harness that work (and share it with other languages) and focus our energies on high-level language features and language-specific optimizations. Not sure if the benefit is worth the cost of doing it, though. Particularly if that cost involves changing the calling conventions and thereby breaking all existing stub libraries. - Michael ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
RE: ocamlopt LLVM support (Was: [Caml-list] OCamlJIT2 vs. OCamlJIT)
Benedikt wrote: So, let's take that LLVM thing to a somewhat more serious level (which means no more arguing with toy projects that simply ignore the difficult stuff). You can learn a lot from prototypes. 3. A better LLVM. If we do it right, other's implementing functional languages using LLVM will not be faced with the same problems again. Dunno if that's possible. What exactly are you thinking of that goes beyond what the other functional languages that already target LLVM have already had to implement? Cheers, Jon. ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs