Google summer of Code proposal

Google summer of Code proposal

[Andrey Riabushenko]

Hi OCaml hackers,

It is not mistake, in spite of ocaml does not take part in GSoC 2009, but 
ocaml community still can benefit from it.

I would like to develop LLVM frontend to Ocaml language. LLVM  does 
participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM 
GSoC project. I want to discuss details with you before I will make an 
official proposal to LLVM.

1.What is the best way to make ocaml frontend on your opinion?

I think the best would to way to develop ocaml llvm front end as a part of 
ocaml distribution. I don't not want to develop yet another a separate 
project, which is half-done llvm frontend that nobody uses. There are plenty 
of those for other languages lying around. I propose to forget about JIT 
capabilities of LLVM and concentrate on AOT compilation for now.

Ocamlopt currently generates native assembler for the following platforms:
i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
I propose to add LLVM assembler generation as another platform to ocamlopt. It 
requires the least modification of ocaml source and easy to maintain. LLVM 
will give ocaml an aggressive whole program optimizer and will make possible 
to run ocaml on new platforms that are supported by LLVM, but not yet by 
Ocaml.


Question to the Ocaml creators and maintainers.
2. Will you merge LLVM platform to the ocaml trunk assuming that it works as 
it should?



Andrey Riabushenko
PhD student,
Faculty of applied mathematics
National technical university of Ukraine "KPI" 
http://kpi.ua/en/

Re: [Caml-list] Google summer of Code proposal

[Seo Sanghyeon]

2009/3/21 Andrey Riabushenko <cdome@bk.ru>:
> I would like to develop LLVM frontend to Ocaml language. LLVM  does
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
> GSoC project. I want to discuss details with you before I will make an
> official proposal to LLVM.

Very cool!

> I think the best would to way to develop ocaml llvm front end as a part of
> ocaml distribution. I don't not want to develop yet another a separate
> project, which is half-done llvm frontend that nobody uses. There are plenty
> of those for other languages lying around. I propose to forget about JIT
> capabilities of LLVM and concentrate on AOT compilation for now.

This sounds reasonable.

> Ocamlopt currently generates native assembler for the following platforms:
> i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
> I propose to add LLVM assembler generation as another platform to ocamlopt. It
> requires the least modification of ocaml source and easy to maintain.

One interesting problem may be that LLVM assembler is typed, while other
assemblers are not.

> LLVM
> will give ocaml an aggressive whole program optimizer and will make possible
> to run ocaml on new platforms that are supported by LLVM, but not yet by
> Ocaml.

Is there any such platform?

> 2. Will you merge LLVM platform to the ocaml trunk assuming that it works as
> it should?

I think it should be (assuming you or someone will continue to maintain it),
but I am in no position to answer this.

-- 
Seo Sanghyeon

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Saturday 21 March 2009 12:39:45 Andrey Riabushenko wrote:
> Hi OCaml hackers,
>
> It is not mistake, in spite of ocaml does not take part in GSoC 2009, but
> ocaml community still can benefit from it.
>
> I would like to develop LLVM frontend to Ocaml language. LLVM  does
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
> GSoC project. I want to discuss details with you before I will make an
> official proposal to LLVM.

I recommend you peruse the LLVM and HLVM mailing lists for information about 
current work along similar lines:

  http://hlvm.forge.ocamlcore.org

> 1. What is the best way to make ocaml frontend on your opinion?

The impedance mismatch between the current OCaml compilers and LLVM is high:

. The OCaml compilers remove type information in the early stages of 
compilation but LLVM is a typed assembler and needs that information to be 
conveyed all the way through to the back end.

. The OCaml compilers make no attempt to provide reusable intermediate 
representations.

So you will probably end up hacking extensively on ocamlopt's internals and, 
consequently, your code will be bound by the QPL license even though you will 
probably not salvage much. This is why I started from scratch.

> I think the best would to way to develop ocaml llvm front end as a part of
> ocaml distribution. I don't not want to develop yet another a separate
> project, which is half-done llvm frontend that nobody uses. There are
> plenty of those for other languages lying around. I propose to forget about
> JIT capabilities of LLVM and concentrate on AOT compilation for now.

JIT is the single most important benefit of LLVM in the context of OCaml. With 
JIT:

. You can instantiate polymorphic definitions for each combination of type 
parameters that they are used with, providing substantial performance 
improvements.

. You can generate code that is optimized for the current machine.

. You can provide a performant top-level.

Forgetting about JIT would certainly be a mistake.

> Ocamlopt currently generates native assembler for the following platforms:
> i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
> I propose to add LLVM assembler generation as another platform to ocamlopt.
> It requires the least modification of ocaml source and easy to maintain.

There are many problems with this:

. You will succumb to ocamlopt's current run-time representation which is 
objectively inefficient (e.g. boxing floats, tuples, records) and was only 
chosen because the compiler lacks capabilities that LLVM already provides for 
you (primarily JIT compilation).

. LLVM's optimization passes will not optimize the representations and, 
consequently, performance will not be improved.

. You will inherit ocamlopt's most serious flaws: its run-time and its FFI.

. If you inherit ocamlopt's run-time then you will need to be able to generate 
compliant code from LLVM which is extremely difficult, error prone and almost 
entirely untested.

> LLVM will give ocaml an aggressive whole program optimizer...

I doubt you could even match the performance of OCaml's existing compiler with 
that approach, much less beat it. There are two reasons for this:

. Building upon ocamlopt's internal run-time representation (e.g. boxed 
tuples) ties LLVM's hands behind its back when it comes to optimization. LLVM 
could do very little to optimize such code.

. LLVM's existing optimization passes work great on naively-generated C or C++ 
code but they know nothing about parametric polymorphism, closures and 
pattern matching. These high-level language features are where the most 
beneficial optimizations lie.

For example, applying LLVM's optimization passes to HLVM generated code only 
give ~15% performance improvements.

> Question to the Ocaml creators and maintainers.
>
> 2. Will you merge LLVM platform to the ocaml trunk assuming that it works
> as it should?

Collaboration with the existing HLVM effort would probably be far more 
productive.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Andrey Riabushenko]

> > LLVM
> > will give ocaml an aggressive whole program optimizer and will make
> > possible to run ocaml on new platforms that are supported by LLVM, but
> > not yet by Ocaml.
>
> Is there any such platform?
>

There are - PIC16, XCore, Cell SPU and Microsoft IL (F# reinvented :).
Many others are under development.

> > 2. Will you merge LLVM platform to the ocaml trunk assuming that it works
> > as it should?
>
> I think it should be (assuming you or someone will continue to maintain
> it), but I am in no position to answer this.

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Saturday 21 March 2009 13:47:40 Andrey Riabushenko wrote:
> > > LLVM
> > > will give ocaml an aggressive whole program optimizer and will make
> > > possible to run ocaml on new platforms that are supported by LLVM, but
> > > not yet by Ocaml.
> >
> > Is there any such platform?
>
> There are - PIC16, XCore, Cell SPU and Microsoft IL (F# reinvented :).
> Many others are under development.

Both OCaml and LLVM support x86, x64 and ARM as well as having backends for 
many other architectures that are of questionable quality. For example, 
LLVM's CIL backend was broken when I tried it and, of course, it cannot even 
support generics because LLVM is incapable of expressing parametric 
polymorphism. For OCaml, there is OCamIL for generating CIL but it also does 
not support parametric polymorphism because it is for .NET 1.1.

I have been developing with LLVM for many months now and I have had two main 
gripes:

1. LLVM calls abort() instead of raising an exception and that makes it almost 
impossible to debug LLVM code because it just dies immediately upon hitting 
any error and gives only the most convoluted contextless error messages. The 
best solution I have found is to litter your LLVM IR emitter with debug 
printfs. HLVM overcomes this problem by catching and handling type errors 
appropriately, making it much easier to use.

2. Many of LLVM's features sound alluring but turn out to be unusable. 
Fortunately, the two core features required to support languages like OCaml 
robustly and efficiently (tail calls and first-class structs) are almost 
completely working. Most of HLVM's development effort has gone into rejecting 
or working around features that do not work correctly in LLVM.

Just to give some examples:

. I found that LLVM's x86 backend breaks tail calls when the return type is a 
first class struct. The workaround is to use sret form, having the caller 
preallocate the return struct and passing a pointer to the struct as an extra 
first argument.

. Lennart Augustsson found that LLVM's vector intrinsics can generate broken 
SSE code for 2D vectors. There is no general workaround: you are expected to 
special-case this situation in all front-ends (!).

. Many people have written to me because they have been unable to get LLVM's 
GC API to work at all. Upon hearing the issues, I immediately opted to use a 
shadow stack designed for an uncooperative environment in HLVM. This at least 
works but it is needlessly inefficient.

. OCaml is vastly superior to C++ for writing compilers but the OCaml bindings 
to LLVM are far from complete. HLVM includes its own auxiliary bindings for 
many important features such as first-class structs and enabling tail calls.

LLVM is a great tool and a wonderful opportunity but it is not a panacea and 
it would be wise to learn such lessons before jumping in to LLVM-based 
development.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Joel Reymont]

On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:

> . You will succumb to ocamlopt's current run-time representation  
> which is
> objectively inefficient (e.g. boxing floats, tuples, records) and  
> was only
> chosen because the compiler lacks capabilities that LLVM already  
> provides for
> you (primarily JIT compilation).


This is probably a stupid suggestion but why not have OCaml directly  
generate machine code, without the use of assembler and linker?

Wouldn't this be easier than trying to couple OCaml with LLVM?

Separately, it's sort of funny that LLVM and its users are going  
through all the trouble now, when Lisp and Forth have had runtime  
compilation for years and years.

---
http://linkedin.com/in/joelreymont

Re: [Caml-list] Google summer of Code proposal

[Joel Reymont]

On Mar 21, 2009, at 2:51 PM, Jon Harrop wrote:

> . I found that LLVM's x86 backend breaks tail calls when the return  
> type is a
> first class struct. The workaround is to use sret form, having the  
> caller
> preallocate the return struct and passing a pointer to the struct as  
> an extra
> first argument.


Returning a structure by having the caller preallocate space, etc. is  
part of the Intel ABI or something like that. This is how it's done,  
period.

Not sure how it relates to breaking tail calls, though.

---
http://linkedin.com/in/joelreymont

Re: Google summer of Code proposal

[Michael Ekstrand]

[-- Attachment #1: Type: text/plain, Size: 1775 bytes --]

Joel Reymont <joelr1@gmail.com> writes:
> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
>
>> . You will succumb to ocamlopt's current run-time representation
>> which is
>> objectively inefficient (e.g. boxing floats, tuples, records) and
>> was only
>> chosen because the compiler lacks capabilities that LLVM already
>> provides for
>> you (primarily JIT compilation).
>
> This is probably a stupid suggestion but why not have OCaml directly
> generate machine code, without the use of assembler and linker?

Because that would duplicate the code and logic provided by the system's
assembler and linker (esp. linker).  For every platform (and there are
many possible combinations!).

If you use the existing linker, then you can depend on the expertise of
the authors for each system getting all the logic right for loading
libraries (which may be arbitrary libraries, when you're using C
extensions) and producing a binary in the correct format for that
system.

Something like LLVM means that OCaml doesn't even need to duplicate the
knowledge about how to generate code for each architecture -- the
compiler author can focus on writing a really good front end, and the
LLVM people can focus on making an excellent machine code generator.  If
compilers can attract the best front-end authors, and projects like LLVM
attract people with the best grasp of optimization and other back-end
matters, then the entire compiler ecosystem benefits more than if these
experts are split amongst many compiler projects.

- Michael

-- 
mouse, n: A device for pointing at the xterm in which you want to type.
Confused by the strange files?  I cryptographically sign my messages.
For more information see <http://www.elehack.net/resources/gpg>.

[-- Attachment #2: Type: application/pgp-signature, Size: 196 bytes --]

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Saturday 21 March 2009 20:49:28 Joel Reymont wrote:
> On Mar 21, 2009, at 2:51 PM, Jon Harrop wrote:
> > . I found that LLVM's x86 backend breaks tail calls when the return
> > type is a
> > first class struct. The workaround is to use sret form, having the
> > caller
> > preallocate the return struct and passing a pointer to the struct as
> > an extra
> > first argument.
>
> Returning a structure by having the caller preallocate space, etc. is
> part of the Intel ABI or something like that. This is how it's done,
> period.

No, not at all. Other calling conventions have many benefits including better 
performance and the ability to return multiple values. LLVM provides a "fast" 
calling convention as well as the (Intel-compatible) C callcc for precisely 
this reason. HLVM uses LLVM's fast callcc. OCaml uses its own non-standard 
calling convention.

Indeed, if HLVM were not using fastcc it would not have any tail calls at all!

This raises some interesting issues. For example, HLVM allows you to declare 
external C functions from your high-level language and call them directly. 
But it also has first-class function pointers so it is necessary to wrap the 
C calls in fastcc calls so the C functions can be used interchangeably with 
internal functions. There are many such subtleties in the design of HLVM and 
I described them all in the relevant OCaml Journal articles.

> Not sure how it relates to breaking tail calls, though.

A design flaw in the implementation of tail calls in LLVM requires code to be 
injected by the architecture-specific code gen after the tail call and before 
the actual return in order to move the struct elements into place. That 
prevents such tail calls from being eliminated later in the code gen.

Fortunately the author was there to assist. Even more remarkably, the same 
student is responsible for tail calls on the JVM (!). He must be busy...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Saturday 21 March 2009 20:43:01 Joel Reymont wrote:
> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
> > . You will succumb to ocamlopt's current run-time representation
> > which is
> > objectively inefficient (e.g. boxing floats, tuples, records) and
> > was only
> > chosen because the compiler lacks capabilities that LLVM already
> > provides for
> > you (primarily JIT compilation).
>
> This is probably a stupid suggestion but why not have OCaml directly
> generate machine code, without the use of assembler and linker?
>
> Wouldn't this be easier than trying to couple OCaml with LLVM?

Had OCaml not already been coupled with LLVM, yes. However, there are quite 
decent OCaml bindings to LLVM already available (in the LLVM tree).

> Separately, it's sort of funny that LLVM and its users are going
> through all the trouble now, when Lisp and Forth have had runtime
> compilation for years and years.

Yes and no. LLVM supports many features that Lisp does not (e.g. type checking 
at compile time, tail calls) and its implementation and the resulting 
performance are far better than any of the open source Lisp implementations.

Lisp was one of the foundations I ruled out for implementing new MLs for these 
reasons.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Fermin Reig]

Andrey Riabushenko wrote:
> 
> I would like to develop LLVM frontend to Ocaml language. 

Sounds cool.

> 1.What is the best way to make ocaml frontend on your opinion?

I haven't been following LLVM, but you can learn about some of the 
issues you are likely to face in my PhD dissertation. Part of the work I 
did was a C-- backend for Ocaml. (Available at 
http://fermin.reig.googlepages.com/reig_phd_2002.pdf)

HTH,
Fermin

Re: [Caml-list] Google summer of Code proposal

[Xavier Leroy]

> I would like to develop LLVM frontend to Ocaml language. LLVM  does 
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM 
> GSoC project. I want to discuss details with you before I will make an 
> official proposal to LLVM. [...]
>
> Do authors of ocaml has something to say about the idea?

Da. A number of things, actually.

1- I know of at least 3, maybe 4 other projects that want to do
something with OCaml and LLVM.  Clearly, some coordination between
these efforts is needed.

2- If you're applying for funding through a summer of code project,
you need to articulate good reasons why you want to combine OCaml and
LLVM.  "Ocaml is cool, LLVM is cool, so OCaml+LLVM would be extra
cool" is not enough.  "It will generate PIC-16 code" isn't either.
Run-time code generation could be a good enough reason, but you still
need to weigh the development cost of the LLVM approach against, for
example, hacking the current OCaml code generator so that it emits
machine code in memory instead of assembly code.

3- A language implementation like OCaml breaks down in four big parts:
        1- Front-end compiler
        2- Back-end compiler and code emitter
        3- Run-time system
        4- OS interface
Of these four, the back-end is not the biggest part nor the most
complicated part.  LLVM gives you part 2, but you still need to
consider the other 3 parts.  Saying "I'll do 1, 3 and 4 from scratch",
Harrop-style, means a 5-year project.  To get somewhere within a
reasonable amount of time, you really need to reuse large parts of the
existing OCaml code base.

4- From a quick look at LLVM specs, the two aspects that appear most
problematic w.r.t. Caml are exception handling and GC interface.
LLVM seems to implement C++/Java "zero-cost" exceptions, which are
known to be quite costly for Caml.  (Been there, done that, in the
early 1990s.)  I regret that LLVM does not provide support for
alternate implementations of exceptions, like the C-- intermediate
language of Ramsey et al does:
   http://portal.acm.org/citation.cfm?id=349337

The big issue, however, is GC interface.  There are GC techniques that
need no support from the back-end: stack maps and conservative
collection.  Stack maps are very costly in execution time.
Conservative GC like the Boehm-Weiser GC is already much better.  But
for full efficiency, back-end support is required.  LLVM documents a
minimal interface to produce stack maps and make them available to the
GC at run-time:
   http://llvm.org/docs/GarbageCollection.html

The first thing you want to investigate is whether this interface is
enough to support an exact, relocating collector such as
OCaml's. According to
   http://www.nabble.com/Garbage-collection-td22219430.html
Gordon Henriksen did succeed in interfacing OCaml's GC with LLVM.
Maybe there is still some more work to do here, in which case I
recommend you look into this first.

6- Here is a schematic of the Caml compiler.  (Use a fixed-width font.)

             |
             | parsing and preprocessing
             v
          Parsetree (untyped AST)
             |
             | type inference and checking
             v
          Typedtree (type-annotated AST)
             |
             | pattern-matching compilation, elimination of modules, classes
             v
          Lambda
           /  \
          /    \ closure conversion, inlining, uncurrying,
         v      \  data representation strategy
      Bytecode   \
                  \
                 Cmm
                  |
                  | code generation
                  v
               Assembly code

In my opinion, the simplest approach is to start at Cmm and generate
LLVM code from there.  Starting at one of the higher-level
intermediate forms would entail reimplementing large chunks of the
OCaml compiler.  Note that Cmm is quite close to the C-- intermediate
language mentioned earlier, so there is a lot to learn from Fermin
Reig's experience with an OCaml/C-- back-end.

7- To finish, I'll preventively deflect some likely reactions by Jon
Harrop:

"But you'll be tied to OCaml's data representation strategy!"
   Right, but 1- implementing you own data representation strategy is
   a lot of work, especially if it is type-based, and 2- OCaml's
   strategy is close to optimal for symbolic computing.

"But LLVM assembly is typed, so you must have types!"
   Just use int32 or int64 as your universal type and cast to
   appropriate pointer types in loads or stores.

"But your code will be tainted by OCaml's evil license!"
   It is trivial to make ocamlopt dump Cmm code in a file or pipe.
   (The -dcmm debug option already does this.)  Then, you can have a
   separate, untainted program that reads the Cmm code and transforms it.

"But shadow stacks are the only way to go for GC interface!"
   No, it's probably the worst approach performance-wise; even a
   conservative GC should work better.

Hope this helps,

- Xavier Leroy

Re: [Caml-list] Re: Google summer of Code proposal

[Kuba Ober]

On Mar 21, 2009, at 5:28 PM, Michael Ekstrand wrote:

> Joel Reymont <joelr1@gmail.com> writes:
>> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
>>
>>> . You will succumb to ocamlopt's current run-time representation
>>> which is
>>> objectively inefficient (e.g. boxing floats, tuples, records) and
>>> was only
>>> chosen because the compiler lacks capabilities that LLVM already
>>> provides for
>>> you (primarily JIT compilation).
>>
>> This is probably a stupid suggestion but why not have OCaml directly
>> generate machine code, without the use of assembler and linker?

This won't help with anything -- why would it? How is this suggestion
relevant to current discussion?

> Because that would duplicate the code and logic provided by the  
> system's
> assembler and linker (esp. linker).  For every platform (and there are
> many possible combinations!).

The only problem is that the usual notion of a "linker" is somewhat  
broken, even if
what we're after is an embedded platform where all of the linking is  
done
before the code hits the target (no run-time linking!).

I will show a trivial example where it fails bad. The example is in C.

Suppose you have two platform-specific registers used to set the DMA  
address.
The platform has 12 bit addresses.

#define DMAL (*((volatile unsigned char*)0xFFA))
#define DMAH (*((volatile unsigned char*)0xFF0))

The DMAL takes a whole least significant byte of the address. The DMAH  
takes
takes one most significant nibble (bits 11:8) of the address, and the  
nibble must be
left-aligned (occupy bits 7:4 of DMAH).

Now, in your code, you want to point DMA to a static buffer. Thusly

void foo(void)
{
   static char buffer[128];
   DMAL = (unsigned char)&buffer;
   DMAH = (((unsigned int)&buffer) >> 4) & 0xF0;
...
}

Now, while all of the addresses are known constants, there's usually  
no way,
in the object file, to tell the linker the expression for the value of  
DMAH!

Thus, instead of what amounts to two "load immediate" instructions,
you have one immediate load, followed by a lot of brouhaha to shift  
and mask what
amounts to constants known at compile/link time. That's what's usually  
called
premature pessimization.

That's one issue with contemporary compile/assemble/link systems.  
Never mind
that even if the assemblers would support such "elaborate" expressions  
using
link-time constants, the compilers don't generate them anyway!

So, writing the code in assembly won't help you! It's only at link  
time that you
know where the buffer[] will end up... You can of course hack and put  
the
buffer at a fixed address -- some C implementations will even have  
special
ways of doing that (say via gcc's __attribute__ mechanism). That will  
backfire as
soon as you get to interface more pieces of code: you'll be spending  
your time
moving stuff around just to keep the memory regions from overlapping  
-- that's the
linker's job, really.

Heck -- many, many assemblers will silently generate utterly wrong  
code for the load
into DMAH, *if* you code this in assembly, not C!! I've got at least a  
dozen production,
shipping assemblers, that silently trip-and-fall on the code like the  
one above. Of course
they only fail if you code it in assembly, as the C compiler won't  
even attempt such
um, "trickery". Silly stuff, really, requiring no advanced  
optimization theories, just doing
one's darn job well...

You have a choice: either put some ASTs into the object file, whenever  
the
expressions involving link-time constants are involved, or you get rid  
of the whole
compile-assemble-link separation and get everything into one place.

The latter, incidentally, is what I ended up doing in my godawful LISP- 
on-its-way-to-ML
platform for Z8 Encore! and SX48.

This would be, "of course", taken care of by a JIT: it would figure  
out that a whole lot
of nothing is done on constant memory addresses, and would replace all  
the operations
by a final load. But, on a platform where the code is statically  
linked on the host, there's
no need for any of that, nor for a JIT. This applies to a whole lot of  
hard-realtime systems
where a lot of reasoning can be made trivial by only using  
preallocated memory, and not
doing any runtime memory allocation (or at least limiting it well).

> If you use the existing linker, then you can depend on the expertise  
> of
> the authors for each system getting all the logic right for loading
> libraries (which may be arbitrary libraries, when you're using C
> extensions) and producing a binary in the correct format for that
> system.

The "logic" present in many linkers is either pretty trivial, or is an  
ugly hack
for lack of expressiveness in object file records. Then you have link  
time optimizations,
which are really trivial to do in a whole-project compiler, but  
require a lot of
extra effort in a linker, etc.

Heck, many linkers use ad-hoc horrible quadratic-or-worse time  
algorithms that backfire
severely once the size of the project gets sufficiently big. Just  
follow the evolution of
gnu ld in face of C++. A farce in multiple acts, at least.

Cheers, Kuba

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Monday 23 March 2009 14:19:00 Xavier Leroy wrote:
> 3- A language implementation like OCaml breaks down in four big parts:
>         1- Front-end compiler
>         2- Back-end compiler and code emitter
>         3- Run-time system
>         4- OS interface
> Of these four, the back-end is not the biggest part nor the most
> complicated part.  LLVM gives you part 2, but you still need to
> consider the other 3 parts.  Saying "I'll do 1, 3 and 4 from scratch",
> Harrop-style, means a 5-year project.

On the contrary, my "style" was to provide the features that I value 
(multicore & FFI) in a usable form (stop-the-world) with the shortest 
possible development time (i.e. <<6 months to create something useful). 
Specifically:

1- Front-end compiler: use camlp4 to provide an embedded DSL for 
high-performance parallel numerics and/or reuse front-ends from existing 
compilers like OCaml, PolyML, MosML, NekoML to build completely new language 
implementations.

2- Back-end compiler and code emitter: reuse LLVM.

3- Run-time system: write the simplest possible precise GC and use 
stop-the-world to apply it to threads that may then run in parallel.

4- OS interface: make it as easy as possible to call C directly.

HLVM had solved (2), (3) and (4) after only 3 months of part-time work. I 
vindicated my style!

> 7- To finish, I'll preventively deflect some likely reactions by Jon
> Harrop:
>
> "But you'll be tied to OCaml's data representation strategy!"
>    Right, but 1- implementing you own data representation strategy is
>    a lot of work, especially if it is type-based, and

Actually I found that easy, not least because I wanted a user-friendly FFI so 
I just used C's data representation whenever possible.

>    2- OCaml's strategy is close to optimal for symbolic computing.

Is MLton not several times faster than OCaml for symbolic computing?

> "But LLVM assembly is typed, so you must have types!"
>    Just use int32 or int64 as your universal type and cast to
>    appropriate pointer types in loads or stores.

That is entirely possible and could be useful as an incremental improvement to 
OCaml's existing bytecode interpreter but it is not a step toward my goals.

> "But your code will be tainted by OCaml's evil license!"
>    It is trivial to make ocamlopt dump Cmm code in a file or pipe.
>    (The -dcmm debug option already does this.)  Then, you can have a
>    separate, untainted program that reads the Cmm code and transforms it.

Again, that is another technically-feasible step away from my goals because 
OCaml's CMM has already been mangled for its data representation (e.g. 31-bit 
ints, boxed floats).

> "But shadow stacks are the only way to go for GC interface!"
>    No, it's probably the worst approach performance-wise; even a
>    conservative GC should work better.

Building a state-of-the-art optimized concurrent GC Leroy-style means an 
infinity-year project. =:-p

Seriously though, I think it is essential to get a first working version of a 
GC that permits parallel threads. HLVM will be useful to a lot of people long 
before its GC gets optimized.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Xavier Leroy]

>>    2- OCaml's strategy is close to optimal for symbolic computing.
> 
> Is MLton not several times faster than OCaml for symbolic computing?

No, only in your dreams.  If there was a Caml or SML compiler that was
twice as fast as Caml on codes like Coq or Isabelle/HOL, everyone (me
included) would have switched to that compiler a long time ago.
MLton can probably outperform Caml on some symbolic codes, but not by
a large factor and not because of data representation strategies (but
rather because of more aggressive inlining and the like).

- Xavier Leroy

Re: [Caml-list] Google summer of Code proposal

[Nicolas Cannasse]

Xavier Leroy a écrit :
>>>    2- OCaml's strategy is close to optimal for symbolic computing.
>>
>> Is MLton not several times faster than OCaml for symbolic computing?
> 
> No, only in your dreams.  If there was a Caml or SML compiler that was
> twice as fast as Caml on codes like Coq or Isabelle/HOL, everyone (me
> included) would have switched to that compiler a long time ago.
> MLton can probably outperform Caml on some symbolic codes, but not by
> a large factor and not because of data representation strategies (but
> rather because of more aggressive inlining and the like).

I agree that OCaml runtime representation is already pretty good, 
although it lacks some runtime inspection abilities.

IMHO, the main optimization that using LLVM can perform wrt OCaml 
internal representation is the ability to fully unbox floats, including 
for FFI callbacks. Of course, that might not help much for symbolic 
processing...

As for 5 years for designing a whole system, thanks to today great tools 
(which OCaml is part of), I was myself able to build a complete 
ecosystem with haXe http://haxe.org and NekoVM in "only" 2 years, I'm 
pretty sure this can be done much faster when people know exactly what 
they are doing on how they want to get there.

Best,
Nicolas

Re: [Caml-list] Google summer of Code proposal

[Joel Reymont]

There's a nice discussion of LLVM in the context of Alice ML here:

http://lambda-the-ultimate.org/node/440

I'm told that not much has changed since.

---
http://tinyco.de
Mac, Lisp, OCaml

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Monday 30 March 2009 16:56:37 Joel Reymont wrote:
> There's a nice discussion of LLVM in the context of Alice ML here:
>
> http://lambda-the-ultimate.org/node/440
>
> I'm told that not much has changed since.

Whoever told you that was wrong: a lot has changed in LLVM over the past five 
years. Indeed, it is one of the most rapidly advancing open source projects 
in existence thanks to extensive contributions from the likes of Apple and 
Google.

LLVM has long since had full support for tail calls. See the "tco" example in 
the "test.ml" file of HLVM for an example. I tested tail calls in LLVM 
extensively before choosing to build upon it. I have found and worked around 
some minor bugs in their TCO implementation but Arnold Schwaighofer just 
committed a fix that will be in LLVM 2.6.

The toy Scheme implementation that was in LLVM five years ago has long since 
been overshadowed by full-blown FPL implementations like the Pure language:

  http://pure-lang.sourceforge.net/

I don't understand Anton van Straaten's other complaint about the lack of 
closures. They are trivial to implement. Again, look at the examples in HLVM 
(although they are hand-coded because we don't have lambda lifting yet).

Moreover, LLVM offers huge advantages:

. LLVM-generated code on x86 is often several times faster and can be up to an 
order of magnitude faster than any existing FPL implementation. Moreover, 
LLVM can JIT compile, making it trivial to outperform interpreted languages 
like OCaml's current top-level. See HLVM's preliminary performance results, 
for example:

http://flyingfrogblog.blogspot.com/2009/03/performance-ocaml-vs-hlvm-beta-04.html

. LLVM generates code very quickly, rivalling ocamlopt's compile times.

. SSE and atomic instructions for high-performance numerics and 
parallelism/concurrency.

. Mature and easy-to-use API with native OCaml bindings.

. Substantial friendly community who not only explain things but fix them for 
you quickly.

. Commercially viable: LLVM is already shipping in products.

LLVM does have some disadvantages:

. LLVM's JIT compiler is not multicore capable (but what FPL implementations 
are?).

. LLVM does not bundle a reusable high-performance concurrent garbage 
collector (but what standalone FPLs do?).

. LLVM's GC API is experimental so if you want a specialized run-time (e.g. 
optimized specifically for symbolics) you have to write it yourself.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Jon Harrop]

On Monday 23 March 2009 14:19:00 Xavier Leroy wrote:
> "But shadow stacks are the only way to go for GC interface!"
>    No, it's probably the worst approach performance-wise; even a
>    conservative GC should work better.

I blogged a quick analysis of the performance of HLVM's current shadow stack 
code:

http://flyingfrogblog.blogspot.com/2009/03/current-shadow-stack-overheads-in-hlvm.html

There is a lot of scope for optimization but these results were enlightening 
to show where the effort should be put. In particular, shadow stack updates 
by the mutator (and not the collector, as I had incorrectly assumed) account 
for the entire performance difference between OCaml and HLVM on the 10-queens 
benchmark.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Google summer of Code proposal

[Andrey Riabushenko]

>This is probably a stupid suggestion but why not have OCaml directly  
>generate machine code, without the use of assembler and linker?

>Wouldn't this be easier than trying to couple OCaml with LLVM?

That is exactly what I am thinking to do. In my opinion, it is least radiсal 
way and it is exactly what is needed to merge the LLVM frontend to the ocaml 
trunk. Ans it is exactly my goal.