Ocamlopt code generator question

Ocamlopt code generator question

[Dmitry Bely]

For amd64 we have in asmcomp/amd64/proc_nt.mlp:

(*  xmm0 - xmm15  100 - 115       xmm0 - xmm9: Caml function arguments
                                xmm0 - xmm3: C function arguments
                                xmm0: Caml and C function results
                                xmm6-xmm15 are preserved by C *)

let loc_arguments arg =
  calling_conventions 0 9 100 109 outgoing arg
let loc_parameters arg =
  let (loc, ofs) = calling_conventions 0 9 100 109 incoming arg in loc
let loc_results res =
  let (loc, ofs) = calling_conventions 0 0 100 100 not_supported res in loc

What these first_float=100 and last_float=109 for loc_arguments and
loc_parameters affect? My impression is that floats are always passed
boxed, so xmm registers are in fact never used to pass parameters. And
float values are returned as a pointer in eax, not a value in xmm0 as
loc_results would suggest.

- Dmitry Bely

Re: Ocamlopt code generator question

[Dmitry Bely]

On Wed, Apr 29, 2009 at 8:28 PM, Jeffrey Scofield
<jeffadm@pythagorion.local> wrote:
> Dmitry Bely <dmitry.bely@gmail.com> writes:
>
>> For amd64 we have in asmcomp/amd64/proc_nt.mlp:
>>
>> (*  xmm0 - xmm15  100 - 115       xmm0 - xmm9: Caml function arguments
>>                                 xmm0 - xmm3: C function arguments
>>                                 xmm0: Caml and C function results
>>                                 xmm6-xmm15 are preserved by C *)
>>
>> let loc_arguments arg =
>>   calling_conventions 0 9 100 109 outgoing arg
>> let loc_parameters arg =
>>   let (loc, ofs) = calling_conventions 0 9 100 109 incoming arg in loc
>> let loc_results res =
>>   let (loc, ofs) = calling_conventions 0 0 100 100 not_supported res in loc
>>
>> What these first_float=100 and last_float=109 for loc_arguments and
>> loc_parameters affect? My impression is that floats are always passed
>> boxed, so xmm registers are in fact never used to pass parameters.
>
> I don't have any experience with amd64, but I have looked at the ARM code
> generator of OCaml 3.10.2.  The first_float and last_float values there are used
> for unboxed calls to internal float functions--most notably, the C standard
> functions like floor().

No - for external C functions loc_external_arguments and
loc_external_results are used. And of course unboxed floats can be
acceptable there. But my question was about loc_arguments and
loc_parameters. E.g. what is the reason to have first_float=100 and
last_float=109 for loc_arguments?

- Dmitry Bely

Re: Ocamlopt code generator question

[Jeffrey Scofield]

Dmitry Bely <dmitry.bely@gmail.com> writes:


> No - for external C functions loc_external_arguments and
> loc_external_results are used. And of course unboxed floats can be
> acceptable there.

Whoops, I was obviously thinking of loc_external_arguments.  I should have
looked at the code again before posting!  Sorry for the confusion, and
thanks for the correction.

Regards,

Jeff Scofield
Seattle

Re: [Caml-list] Ocamlopt code generator question

[Xavier Leroy]

> For amd64 we have in asmcomp/amd64/proc_nt.mlp:
> 
> (*  xmm0 - xmm15  100 - 115       xmm0 - xmm9: Caml function arguments
>                                 xmm0 - xmm3: C function arguments
>                                 xmm0: Caml and C function results
>                                 xmm6-xmm15 are preserved by C *)
> 
> let loc_arguments arg =
>   calling_conventions 0 9 100 109 outgoing arg
> let loc_parameters arg =
>   let (loc, ofs) = calling_conventions 0 9 100 109 incoming arg in loc
> let loc_results res =
>   let (loc, ofs) = calling_conventions 0 0 100 100 not_supported res in loc
> 
> What these first_float=100 and last_float=109 for loc_arguments and
> loc_parameters affect? My impression is that floats are always passed
> boxed, so xmm registers are in fact never used to pass parameters. And
> float values are returned as a pointer in eax, not a value in xmm0 as
> loc_results would suggest.

The ocamlopt code generators support unboxed floats as function
parameters and results, as well as returning multiple results in
several registers.  (Except for the x86-32 bits port, because of the
weird floating-point model of this architecture.)  You're right that
the ocamlopt "middle-end" does not currently take advantage of this
possibility, since floats are passed between functions in boxed state.

- Xavier Leroy

Re: [Caml-list] Ocamlopt code generator question

[Dmitry Bely]

On Tue, May 5, 2009 at 1:24 PM, Xavier Leroy <Xavier.Leroy@inria.fr> wrote:
>> For amd64 we have in asmcomp/amd64/proc_nt.mlp:
>>
>> (*  xmm0 - xmm15  100 - 115       xmm0 - xmm9: Caml function arguments
>>                                xmm0 - xmm3: C function arguments
>>                                xmm0: Caml and C function results
>>                                xmm6-xmm15 are preserved by C *)
>>
>> let loc_arguments arg =
>>  calling_conventions 0 9 100 109 outgoing arg
>> let loc_parameters arg =
>>  let (loc, ofs) = calling_conventions 0 9 100 109 incoming arg in loc
>> let loc_results res =
>>  let (loc, ofs) = calling_conventions 0 0 100 100 not_supported res in loc
>>
>> What these first_float=100 and last_float=109 for loc_arguments and
>> loc_parameters affect? My impression is that floats are always passed
>> boxed, so xmm registers are in fact never used to pass parameters. And
>> float values are returned as a pointer in eax, not a value in xmm0 as
>> loc_results would suggest.
>
> The ocamlopt code generators support unboxed floats as function
> parameters and results, as well as returning multiple results in
> several registers.  (Except for the x86-32 bits port, because of the
> weird floating-point model of this architecture.)  You're right that
> the ocamlopt "middle-end" does not currently take advantage of this
> possibility, since floats are passed between functions in boxed state.

I see. Why I asked this: trying to improve floating-point performance
on 32-bit x86 platform I have merged floating-point SSE2 code
generator from amd64 ocamlopt back end to i386 one, making ia32sse2
architecture. It also inlines sqrt() via -ffast-math flag and slightly
optimizes emit_float_test (usually eliminates an extra jump) -
features that are missed in the original amd64 code generator. All
this seems to work OK: beyond my own code all tests found in Ocaml CVS
test directory are passed. Of course this is idea is not new - you had
working IA32+SSE2 back end several years ago [1] but unfortunately
never released it to the public.

Is this of any interest to anybody?

- Dmitry Bely

[1] http://caml.inria.fr/pub/ml-archives/caml-list/2003/03/e0db2f3f54ce19e4bad589ffbb082484.fr.html

Re: [Caml-list] Ocamlopt code generator question

[Jean-Marc Eber]

Hi Dimitry,

LexiFi for instance _is_ clearly interested by a sse2 32bit code generator.

One should probably have the following in mind and/or ask the following questions:

- it is probably not a good idea to support both backends (sse2 and old stack fp 
i386 architecture). It will be necessary to make a choice (especially taking in 
account the limited INRIA resources and the burden of already supporting 
different windows ports).

- would INRIA be ok to switch to a sse2 code generator (based on Dimitry's patch 
- supposing that he is ok to donate it to INRIA - or Xavier's work or whatever)?

- I also guess that a sse2 code generator would be simpler than the current one 
(that has to support this horrible fp stack architecture) and would therefore be 
a better candidate for further enhancements.

- what is the opinion on this list, as a switch to a sse2 backend would exclude 
"old" processors from being OCaml compatible (I don't have a precise list at 
hand for now) ?

My opinion is that this support of legacy hardware is not important, but I guess 
others are arguing in opposite directions... :-)

But again, having better floating point performance (and predictable behaviour, 
compared to the bytecode version) would be a big plus for some applications.

Best regards,

Jean-Marc




Dmitry Bely a écrit :
> 
> I see. Why I asked this: trying to improve floating-point performance
> on 32-bit x86 platform I have merged floating-point SSE2 code
> generator from amd64 ocamlopt back end to i386 one, making ia32sse2
> architecture. It also inlines sqrt() via -ffast-math flag and slightly
> optimizes emit_float_test (usually eliminates an extra jump) -
> features that are missed in the original amd64 code generator. All
> this seems to work OK: beyond my own code all tests found in Ocaml CVS
> test directory are passed. Of course this is idea is not new - you had
> working IA32+SSE2 back end several years ago [1] but unfortunately
> never released it to the public.
> 
> Is this of any interest to anybody?
> 
> - Dmitry Bely
> 
> [1] http://caml.inria.fr/pub/ml-archives/caml-list/2003/03/e0db2f3f54ce19e4bad589ffbb082484.fr.html
> 
> _______________________________________________
> 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 code generator question

[Sylvain Le Gall]

On 05-05-2009, Jean-Marc Eber <jeanmarc.eber@lexifi.com> wrote:
> Hi Dimitry,
>
> LexiFi for instance _is_ clearly interested by a sse2 32bit code generator.
>
> One should probably have the following in mind and/or ask the following questions:
>
> - it is probably not a good idea to support both backends (sse2 and old stack fp 
> i386 architecture). It will be necessary to make a choice (especially taking in 
> account the limited INRIA resources and the burden of already supporting 
> different windows ports).
>

Maybe this point can be discussed. I think 3 ports for windows is a bit
too much... I don't know Dimitry point of view, but maybe INRIA can just
consider MSVC (or mingw). If this is a way to free INRIA resources, it
is a good option.

> - would INRIA be ok to switch to a sse2 code generator (based on Dimitry's patch 
>   supposing that he is ok to donate it to INRIA - or Xavier's work or whatever)?
>
> - I also guess that a sse2 code generator would be simpler than the current one 
> (that has to support this horrible fp stack architecture) and would therefore be 
> a better candidate for further enhancements.
>
> - what is the opinion on this list, as a switch to a sse2 backend would exclude 
> "old" processors from being OCaml compatible (I don't have a precise list at 
> hand for now) ?

I would like to say "go on", but SSE2 will limit OCaml to P4 on i386.
In Debian, this is the "low limit" of our build daemon. I think it is
quite dangerous not having the option of the older code generator...

If INRIA choose to switch to SSE2 there should be at least still a way
to compile on older architecture. Doesn't mean that INRIA need to keep
the old code generator, but should provide a simple emulation for it. In
this case, we will have good performance on new arch for float and we
will still be able to compile on old arch. 

>
> My opinion is that this support of legacy hardware is not important, but I guess 
> others are arguing in opposite directions... :-)
>

I would say that "the performance of legacy hardware is not important"
-- support is still important. 

> But again, having better floating point performance (and predictable behaviour, 
> compared to the bytecode version) would be a big plus for some applications.
>

Indeed.

Regards
Sylvain Le Gall

Re: [Caml-list] Ocamlopt code generator question

[Jon Harrop]

On Tuesday 05 May 2009 15:15:33 Jean-Marc Eber wrote:
> Hi Dimitry,
>
> LexiFi for instance _is_ clearly interested by a sse2 32bit code generator.
>
> One should probably have the following in mind and/or ask the following
> questions:
>
> - it is probably not a good idea to support both backends (sse2 and old
> stack fp i386 architecture). It will be necessary to make a choice
> (especially taking in account the limited INRIA resources and the burden of
> already supporting different windows ports).
>
> - would INRIA be ok to switch to a sse2 code generator (based on Dimitry's
> patch - supposing that he is ok to donate it to INRIA - or Xavier's work or
> whatever)?
>
> - I also guess that a sse2 code generator would be simpler than the current
> one (that has to support this horrible fp stack architecture) and would
> therefore be a better candidate for further enhancements.
>
> - what is the opinion on this list, as a switch to a sse2 backend would
> exclude "old" processors from being OCaml compatible (I don't have a
> precise list at hand for now) ?
>
> My opinion is that this support of legacy hardware is not important, but I
> guess others are arguing in opposite directions... :-)
>
> But again, having better floating point performance (and predictable
> behaviour, compared to the bytecode version) would be a big plus for some
> applications.

If the idea is to provide better code generation on x86 going forwards with 
minimal effort then I'd have thought an LLVM-based backend would be the 
obvious choice. My tests with HLVM showed that numerical code can be a 
whopping 8x faster than today's ocamlopt on x86 and, of course, LLVM is 
improving much more rapidly.

LLVM can probably replace the x86, x64 and ppc backends. LLVM also seems like 
a sane approach to providing a native-code top level via its existing JIT 
functionality.

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

RE: [Caml-list] Re: Ocamlopt code generator question

[David Allsopp]

Sylvain Le Gall wrote:
> Maybe this point can be discussed. I think 3 ports for windows is a bit
> too much... I don't know Dimitry point of view, but maybe INRIA can
> just consider MSVC (or mingw). If this is a way to free INRIA resources,
it
> is a good option.

There are actually 4 Windows ports if you include MSVC64! I'm not sure at
this stage that it's possible to reduce the number - I think you'll find
that there are enough users on both sides with enough
hard/impossible-to-work-around requirements (probably to do with external
libraries) such that you'd never be able to decide between just MinGW or
just MSVC. The Cygwin port, although obviously requiring extra work and
support, is more like supporting a separate flavour of UNIX than a separate
Windows port, I think.

> I would like to say "go on", but SSE2 will limit OCaml to P4 on i386.
> In Debian, this is the "low limit" of our build daemon. I think it is
> quite dangerous not having the option of the older code generator...

+1 I've still got a few quite useable Pentium 3 machines knocking around...
it would seem a shame if a lack of compiler rather than OS support ever
caused them to be retired. That said, the power and noise will probably be
what retires them first...



David

Re: [Caml-list] Re: Ocamlopt code generator question

[Dmitry Bely]

On Tue, May 5, 2009 at 6:58 PM, Sylvain Le Gall <sylvain@le-gall.net> wrote:
> On 05-05-2009, Jean-Marc Eber <jeanmarc.eber@lexifi.com> wrote:
>> Hi Dimitry,
>>
>> LexiFi for instance _is_ clearly interested by a sse2 32bit code generator.
>>
>> One should probably have the following in mind and/or ask the following questions:
>>
>> - it is probably not a good idea to support both backends (sse2 and old stack fp
>> i386 architecture). It will be necessary to make a choice (especially taking in
>> account the limited INRIA resources and the burden of already supporting
>> different windows ports).
>>
>
> Maybe this point can be discussed. I think 3 ports for windows is a bit
> too much... I don't know Dimitry point of view, but maybe INRIA can just
> consider MSVC (or mingw). If this is a way to free INRIA resources, it
> is a good option.

You should ask Xavier but I personally don't think that two Windows
ports (Cygwin is quite a different beast) are really the problem for
INRIA. They use (almost) the same C runtime library, the same
makefiles and I don't know a single Ocaml bug that was MSVC or Mingw
specific.

Yes, you have two different emit_nt.mlp and emit.mlp, but the only way
to make things simpler is to abandon MASM syntax completely. In
principle it's possible - GNU as under Windows generates the same COFF
files as MASM, although many Windows people that are not familiar with
AT&T syntax would not be very glad...

>> - would INRIA be ok to switch to a sse2 code generator (based on Dimitry's patch
>>   supposing that he is ok to donate it to INRIA - or Xavier's work or whatever)?
>>
>> - I also guess that a sse2 code generator would be simpler than the current one
>> (that has to support this horrible fp stack architecture) and would therefore be
>> a better candidate for further enhancements.
>>
>> - what is the opinion on this list, as a switch to a sse2 backend would exclude
>> "old" processors from being OCaml compatible (I don't have a precise list at
>> hand for now) ?
>
> I would like to say "go on", but SSE2 will limit OCaml to P4 on i386.
> In Debian, this is the "low limit" of our build daemon. I think it is
> quite dangerous not having the option of the older code generator...

I also would like to retain support for i386. Hopefully, one more code
generator (mostly a copy/paste combination of two already existing
ones) would not require too much efforts to support.

> If INRIA choose to switch to SSE2 there should be at least still a way
> to compile on older architecture. Doesn't mean that INRIA need to keep
> the old code generator, but should provide a simple emulation for it. In
> this case, we will have good performance on new arch for float and we
> will still be able to compile on old arch.
>
>>
>> My opinion is that this support of legacy hardware is not important, but I guess
>> others are arguing in opposite directions... :-)
>>
>
> I would say that "the performance of legacy hardware is not important"
> -- support is still important.
>
>> But again, having better floating point performance (and predictable behaviour,
>> compared to the bytecode version) would be a big plus for some applications.
>>
>
> Indeed.

Don't quite understand what is "predictable behavior" - any generator
should conform to specs. In my tests x87 and SSE2 backends show the
same results (otherwise it would be called a bug).

- Dmitry Bely

Re: [Caml-list] Re: Ocamlopt code generator question

[Dmitry Bely]

On Tue, May 5, 2009 at 8:06 PM, Jean-Marc Eber <jeanmarc.eber@lexifi.com> wrote:
> Hi Dimitry,
>
> Firstly thanks for looking again at the sse2 stuff!
>
> A difference may occur, if I'm not wrong, from the intermediate results
> precision:
>
> in sse2, eveything is done on 8 bytes (if you "do" doubles at least), while,
> in x87, intermdiate results (kept on the stack) are 10 bytes precision.
>
> This may result in differences (and the bytecode runtime never uses x87
> intermediate storage, so it behaves _numerically_ like the sse2 code
> generator, I guess).

I wouldn't be so sure. Bytecode runtime is C compiler-dependent (that
does use x87 for floating-point calculations), so rounding errors can
lead to different results. Floating point is always approximate...

- Dmitry Bely

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Xavier Leroy]

Dmitry Bely wrote:

> I see. Why I asked this: trying to improve floating-point performance
> on 32-bit x86 platform I have merged floating-point SSE2 code
> generator from amd64 ocamlopt back end to i386 one, making ia32sse2
> architecture. It also inlines sqrt() via -ffast-math flag and slightly
> optimizes emit_float_test (usually eliminates an extra jump) -
> features that are missed in the original amd64 code generator.

You just passed black belt in OCaml compiler hacking :-)

> Is this of any interest to anybody?

I'm definitely interested in the potential improvements to the amd64
code generator.

Concerning the i386 code generator (x86 in 32-bit mode), SSE2 float
arithmetic does improve performance and fit ocamlopt's compilation
model much better than the current x87 float arithmetic, which is a
bit of a hack.  Several options can be considered:

1- Have an additional "ia32sse2" port of ocamlopt in parallel with the
   current "i386" port.

2- Declare pre-SSE2 processors obsolete and convert the current
   "i386" port to always use SSE2 float arithmetic.

3- Support both x87 and SSE2 float arithmetic within the same i386
   port, with a command-line option to activate SSE2, like gcc does.

I'm really not keen on approach 1.  We have too many ports (and
their variants for Windows/MSVC) already.  Moreover, I suspect
packagers would stick to the i386 port for compatibility with old
hardware, and most casual users would, too, out of lazyness, so this
hypothetical "ia32sse2" port would receive little testing.

Approach 2 is tempting for me because it would simplify the x86-32
code generator and remove some historical cruft.  The issue is that it
demands a processor that implements SSE2.  For a list of processors, see
  http://en.wikipedia.org/wiki/SSE2
As a rule of thumb, almost all desktop PC bought since 2004 has SSE2,
as well as almost all notebooks since 2006.  That should be OK for
professional users (it's nearly impossible to purchase maintenance
beyond 3 years, anyway) and serious hobbyists.  However, packagers are
going to be very unhappy: Debian still lists i486 as its bottom line;
for Fedora, it's Pentium or Pentium II; for Windows, it's "a 1GHz
processor", meaning Pentium III.  All these processors lack SSE2
support.  Only MacOS X is SSE2-compatible from scratch.

Approach 3 is probably the best from a user's point of view.  But it's
going to complicate the code generator: the x87 cruft would still be
there, and new cruft would need to be added to support SSE2.  Code
compiled with the SSE2 flag could link with code compiled without,
provided the SSE2 registers are not used for parameter and result
passing.  But as Dmitry observed, this is already the case in the
current ocamlopt compiler.

Jean-Marc Eber:
>> But again, having better floating point performance (and
>> predictable behaviour, compared to the bytecode version) would be a
>> big plus for some applications.

Dmitry Bely:
> Don't quite understand what is "predictable behavior" - any generator
> should conform to specs. In my tests x87 and SSE2 backends show the
> same results (otherwise it would be called a bug).

You haven't tested enough :-).  The x87 backend keeps some intermediate
results in 80-bit float format, while the SSE2 backend (as well as all
other backends and the bytecode interpreter) compute everything in
64-bit format.  See David Monniaux's excellent tutorial:
  http://hal.archives-ouvertes.fr/hal-00128124/en/
Computing intermediate results in extended precision has pros and
cons, but my understanding is that the cons slightly outweigh the pros.

- Xavier Leroy

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[David MENTRE]

Hello,

Xavier Leroy <Xavier.Leroy@inria.fr> writes:

> 1- Have an additional "ia32sse2" port of ocamlopt in parallel with the
>    current "i386" port.
>
> 2- Declare pre-SSE2 processors obsolete and convert the current
>    "i386" port to always use SSE2 float arithmetic.
>
> 3- Support both x87 and SSE2 float arithmetic within the same i386
>    port, with a command-line option to activate SSE2, like gcc does.

Regarding option 2, I assume that byte-code would still work on i386
pre-SSE2 machines? So OCaml programs would still work on those machines.

As far as I know, one is using ocamlopt to improve performance. I can't
think of any case where one would need native code running on pre-SS2
machines which are so outdated performance-wise.

So I would vote for option 2: always use SSE2 float arithmetic.

Sincerely yours,
david
-- 
GPG/PGP key: A3AD7A2A David MENTRE <dmentre@linux-france.org>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Matteo Frigo]

Do you guys have any sort of empirical evidence that scalar SSE2 math is
faster than plain old x87?

I ask because every time I tried compiling FFTW with gcc -m32
-mfpmath=sse, the result has been invariably slower than the vanilla x87
compilation.  (I am talking about scalar arithmetic here.  FFTW also
supports SSE2 2-way vector arithmetic, which is of course faster.)

I also remember trying similar experiments with other numerical code in
the Pentium 4 dark ages, with similar results.  I don't see any reason
why this should be the case, and maybe this is just a problem of gcc,
but I don't think you should automatically assume that SSE2 math is
faster without running a few experiments first.

Regards,
Matteo Frigo

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Sunday 10 May 2009 12:04:13 David MENTRE wrote:
> Regarding option 2, I assume that byte-code would still work on i386
> pre-SSE2 machines? So OCaml programs would still work on those machines.
>
> As far as I know, one is using ocamlopt to improve performance. I can't
> think of any case where one would need native code running on pre-SS2
> machines which are so outdated performance-wise.
>
> So I would vote for option 2: always use SSE2 float arithmetic.

Note that you can use the same argument to justify not optimizing the x86 
backend because power users should be using the (much more performant) x64 
code gen.

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

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Monday 11 May 2009 00:12:49 Matteo Frigo wrote:
> Do you guys have any sort of empirical evidence that scalar SSE2 math is
> faster than plain old x87?

I believe the motivation is to make good performance tractible in ocamlopt so 
it is more about the ease of code generation rather than the inherent 
performance characteristics of the two approaches.

> I ask because every time I tried compiling FFTW with gcc -m32
> -mfpmath=sse, the result has been invariably slower than the vanilla x87
> compilation.  (I am talking about scalar arithmetic here.  FFTW also
> supports SSE2 2-way vector arithmetic, which is of course faster.)
>
> I also remember trying similar experiments with other numerical code in
> the Pentium 4 dark ages, with similar results.  I don't see any reason
> why this should be the case, and maybe this is just a problem of gcc,
> but I don't think you should automatically assume that SSE2 math is
> faster without running a few experiments first.

As I understand it, this is very much a problem with ocamlopt and not with 
gcc. Specifically, floating point code compiled by ocamlopt on x86 gives 
mediocre performance for unknown reasons. Hence there is a desire to use more 
modern solutions that simplify the generation of performant code.

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

Re: Ocamlopt x86-32 and SSE2

[Stefan Monnier]

> As far as I know, one is using ocamlopt to improve performance.
> I can't think of any case where one would need native code running on
> pre-SS2 machines which are so outdated performance-wise.

You mean we should make slow machines even slower?


        Stefan

Re: [Caml-list] Re: Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Monday 11 May 2009 04:43:21 Stefan Monnier wrote:
> > As far as I know, one is using ocamlopt to improve performance.
> > I can't think of any case where one would need native code running on
> > pre-SS2 machines which are so outdated performance-wise.
>
> You mean we should make slow machines even slower?

Old machines can still run old versions of OCaml at full speed.

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

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Dmitry Bely]

On Fri, May 8, 2009 at 2:21 PM, Xavier Leroy <Xavier.Leroy@inria.fr> wrote:

>> I see. Why I asked this: trying to improve floating-point performance
>> on 32-bit x86 platform I have merged floating-point SSE2 code
>> generator from amd64 ocamlopt back end to i386 one, making ia32sse2
>> architecture. It also inlines sqrt() via -ffast-math flag and slightly
>> optimizes emit_float_test (usually eliminates an extra jump) -
>> features that are missed in the original amd64 code generator.
>
> You just passed black belt in OCaml compiler hacking :-)

Thank you, sensei :-)

>> Is this of any interest to anybody?
>
> I'm definitely interested in the potential improvements to the amd64
> code generator.
>
> Concerning the i386 code generator (x86 in 32-bit mode), SSE2 float
> arithmetic does improve performance and fit ocamlopt's compilation
> model much better than the current x87 float arithmetic, which is a
> bit of a hack.  Several options can be considered:
>
> 1- Have an additional "ia32sse2" port of ocamlopt in parallel with the
>   current "i386" port.
>
> 2- Declare pre-SSE2 processors obsolete and convert the current
>   "i386" port to always use SSE2 float arithmetic.
>
> 3- Support both x87 and SSE2 float arithmetic within the same i386
>   port, with a command-line option to activate SSE2, like gcc does.
>
> I'm really not keen on approach 1.  We have too many ports (and
> their variants for Windows/MSVC) already.  Moreover, I suspect
> packagers would stick to the i386 port for compatibility with old
> hardware, and most casual users would, too, out of lazyness, so this
> hypothetical "ia32sse2" port would receive little testing.
>
> Approach 2 is tempting for me because it would simplify the x86-32
> code generator and remove some historical cruft.  The issue is that it
> demands a processor that implements SSE2.  For a list of processors, see
>  http://en.wikipedia.org/wiki/SSE2
> As a rule of thumb, almost all desktop PC bought since 2004 has SSE2,
> as well as almost all notebooks since 2006.  That should be OK for
> professional users (it's nearly impossible to purchase maintenance
> beyond 3 years, anyway) and serious hobbyists.  However, packagers are
> going to be very unhappy: Debian still lists i486 as its bottom line;
> for Fedora, it's Pentium or Pentium II; for Windows, it's "a 1GHz
> processor", meaning Pentium III.  All these processors lack SSE2
> support.  Only MacOS X is SSE2-compatible from scratch.
>
> Approach 3 is probably the best from a user's point of view.  But it's
> going to complicate the code generator: the x87 cruft would still be
> there, and new cruft would need to be added to support SSE2.  Code
> compiled with the SSE2 flag could link with code compiled without,
> provided the SSE2 registers are not used for parameter and result
> passing.  But as Dmitry observed, this is already the case in the
> current ocamlopt compiler.

I am curious if passing unboxed floats is possible in the current
Ocaml data model?

As for proposed options - I tend to vote for #3 (and implement it if
there is a consensus). Still there is a plenty of low-power/embedded
x86 hardware that does not support SSE2. And one will be able to
compare x87 and SSE2 backends performance to convince him/herself that
the play really worths the candle :-)

- Dmitry Bely

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Florian Weimer]

* Xavier Leroy:

> To finish: I'm still very interested in hearing from packagers.  Does
> Debian, for example, already have some packages that are SSE2-only?

Not to my knowledge (it would be a bug).  Some packages use JITting or
dynamic shared objects to provide optimized code.

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Richard Jones]

On Tue, May 12, 2009 at 11:37:17AM +0200, Xavier Leroy wrote:
> Richard Jones:
> >AMD Geode then ...
> 
> Apparently, recent versions of the Geode support SSE2 as well.
> Low-power people love vector instruction sets, because it lets them do
> common tasks like audio and video decoding more efficiently, ergo with
> less energy.

I was mostly joking about this - don't worry :-)

> Well, either
> that, or rely on the kernel to trap unimplemented SSE2 instructions
> and emulate them in software.  This is theoretically possible but I'm
> pretty sure neither Linux nor Windows implement it.

<aside>
Even VMWare aren't doing this.  However, it's now relatively common to
have the CPU lie about the true capabilities of its instruction set
(by faking the return from CPUID, which in Linux means that
/proc/cpuinfo flags doesn't give the true picture).  This is done so
that guests can be migrated across machines in a cluser which have
different capabilities.  VMWare called this 'EVC clustering'.
</aside>

> To finish: I'm still very interested in hearing from packagers.  Does
> Debian, for example, already have some packages that are SSE2-only?
> Are these packages specially tagged so that the installer will refuse
> to install them on pre-SSE2 hardware?  What's the party line?

>From the Fedora p.o.v., there's no problem.  We'll just deprecate
OCaml on ancient pre-SSE2 hardware (for new distributions - they can
keep using RHEL 5 on older hardware).

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Xavier Leroy]

This is an interesting discussion with many relevant points being
made.  Some comments:

Matteo Frigo:
> Do you guys have any sort of empirical evidence that scalar SSE2 math is
> faster than plain old x87?
> I ask because every time I tried compiling FFTW with gcc -m32
> -mfpmath=sse, the result has been invariably slower than the vanilla x87
> compilation.  (I am talking about scalar arithmetic here.  FFTW also
> supports SSE2 2-way vector arithmetic, which is of course faster.)

gcc does rather clever tricks with the x87 float stack and the fxch
instruction, making it look almost like a flat register set and
managing to expose some instruction-level parallelism despite the
dependencies on the top of the stack.  In contrast, ocamlopt uses the
x87 stack in a pedestrian, reverse-Polish-notation way, so the
benefits of having "real" float registers is bigger.

Using the experimental x86-sse2 port that I did in 2003 on a Core2
processor, I see speedups of 10 to 15% on my few standard float
benchmarks.  However, these benchmarks were written in such a way that
the generated x87 code isn't too awful.  It is easy to construct
examples where the SSE2 code is twice as fast as x87.

More generally, the SSE2 code generator is much more forgiving towards
changes in program style, and its performance characteristics are more
predictable than the x87 code generator.  For instance, manual
elimination of common subexpressions is almost always a win with SSE2
but quite often a loss with x87 ...

Pascal Cuoq:
> According to http://en.wikipedia.org/wiki/SSE2, someone using a Via C7
> should be fine.

Richard Jones:
> AMD Geode then ...

Apparently, recent versions of the Geode support SSE2 as well.
Low-power people love vector instruction sets, because it lets them do
common tasks like audio and video decoding more efficiently, ergo with
less energy.

Sylvain Le Gall:
> If INRIA choose to switch to SSE2 there should be at least still a way
> to compile on older architecture. Doesn't mean that INRIA need to keep
> the old code generator, but should provide a simple emulation for it. In
> this case, we will have good performance on new arch for float and we
> will still be able to compile on old arch. 

The least complicated way to preserve backward compatibility with
pre-SSE2 hardware is to keep the existing x87 code generator and bolt
the SSE2 generator on top of it, Frankenstein-style.  Well, either
that, or rely on the kernel to trap unimplemented SSE2 instructions
and emulate them in software.  This is theoretically possible but I'm
pretty sure neither Linux nor Windows implement it.

David Mentre:
> Regarding option 2, I assume that byte-code would still work on i386
> pre-SSE2 machines? So OCaml programs would still work on those machines.

You're correct, provided the bytecode interpreter isn't compiled in
SSE2 mode itself (see below for one reason one might want to do this).
However, packagers would still be unhappy about this: packaged OCaml
applications like Unison or Coq are usually compiled to native-code
(the additional speed is most welcome in the case of Coq...).
Therefore, packagers would have to choose between making these
applications SSE2-only or make them slower by compiling them to bytecode.

Dmitry Bely:
> [Reproducibility of results between bytecode and native]
> I wouldn't be so sure. Bytecode runtime is C compiler-dependent (that
> does use x87 for floating-point calculations), so rounding errors can
> lead to different results.

That's right: even though it stores all intermediate float results in
64-bit format, a bytecode interpreter compiled in default x87 mode still
exhibits double rounding anomalies.  One would have to compile it with
gcc in SSE2 mode (like MacOS X does by default) to have complete
reproducibility between bytecode and native.

> Floating point is always approximate...

I used to believe strongly in this viewpoint, but after discussion
with people who do static analysis or program proof over float
programs, I'm not so sure: static analysis and program proof are
difficult enough that one doesn't want to complicate them even further
to take extended-precision intermediate results and double rounding
into account...

To finish: I'm still very interested in hearing from packagers.  Does
Debian, for example, already have some packages that are SSE2-only?
Are these packages specially tagged so that the installer will refuse
to install them on pre-SSE2 hardware?  What's the party line?

- Xavier Leroy

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Monday 11 May 2009 09:43:59 Dmitry Bely wrote:
> So it's just pie in the sky. No working implementation has been
> demonstrated since then.

The file "test/CodeGen/Generic/GC/simple_ocaml.ll" in the LLVM 2.5 source 
distribution contains the following test code for the OCaml-compatible 
frametable emitter:

  %struct.obj = type { i8*, %struct.obj* }
  
  define %struct.obj* @fun(%struct.obj* %head) gc "ocaml" {
  entry:
          %gcroot.0 = alloca i8*
          %gcroot.1 = alloca i8*
          
          call void @llvm.gcroot(i8** %gcroot.0, i8* null)
          call void @llvm.gcroot(i8** %gcroot.1, i8* null)
          
          %local.0 = bitcast i8** %gcroot.0 to %struct.obj**
          %local.1 = bitcast i8** %gcroot.1 to %struct.obj**
  
          store %struct.obj* %head, %struct.obj** %local.0
          br label %bb.loop
  bb.loop:
          %t0 = load %struct.obj** %local.0
          %t1 = getelementptr %struct.obj* %t0, i32 0, i32 1
          %t2 = bitcast %struct.obj* %t0 to i8*
          %t3 = bitcast %struct.obj** %t1 to i8**
          %t4 = call i8* @llvm.gcread(i8* %t2, i8** %t3)
          %t5 = bitcast i8* %t4 to %struct.obj*
          %t6 = icmp eq %struct.obj* %t5, null
          br i1 %t6, label %bb.loop, label %bb.end
  bb.end:
          %t7 = malloc %struct.obj
          store %struct.obj* %t7, %struct.obj** %local.1
          %t8 = bitcast %struct.obj* %t7 to i8*
          %t9 = load %struct.obj** %local.0
          %t10 = getelementptr %struct.obj* %t9, i32 0, i32 1
          %t11 = bitcast %struct.obj* %t9 to i8*
          %t12 = bitcast %struct.obj** %t10 to i8**
          call void @llvm.gcwrite(i8* %t8, i8* %t11, i8** %t12)
          ret %struct.obj* %t7
  }
  
  declare void @llvm.gcroot(i8** %value, i8* %tag)
  declare void @llvm.gcwrite(i8* %value, i8* %obj, i8** %field)
  declare i8* @llvm.gcread(i8* %obj, i8** %field)

Compiling this with:

  llvm-as <simple_ocaml.ll | llc

gives:

          .file	"<stdin>"
          .text
          .globl	caml<stdin>__code_begin
  caml<stdin>__code_begin:
          .data
          .globl	caml<stdin>__data_begin
  caml<stdin>__data_begin:
  
          .text
          .align	16
          .globl	fun
          .type	fun,@function
  fun:
  .Leh_func_begin1:
  .Llabel1:
          subl	$12, %esp
          movl	$0, 8(%esp)
          movl	$0, 4(%esp)
          movl	16(%esp), %eax
          movl	%eax, 8(%esp)
          .align	16
  .LBB1_1:	# bb.loop
          movl	8(%esp), %eax
          cmpl	$0, 4(%eax)
          je	.LBB1_1	# bb.loop
  .LBB1_2:	# bb.end
          movl	$8, (%esp)
          call	malloc
  .Llabel2:
          movl	%eax, 4(%esp)
          movl	8(%esp), %ecx
          movl	%eax, 4(%ecx)
          addl	$12, %esp
          ret
          .size	fun, .-fun
  .Leh_func_end1:
          .section	.eh_frame,"aw",@progbits
  .LEH_frame0:
  .Lsection_eh_frame:
  .Leh_frame_common:
          .long	.Leh_frame_common_end-.Leh_frame_common_begin
  .Leh_frame_common_begin:
          .long	0x0
          .byte	0x1
          .asciz	"zR"
          .uleb128	1
          .sleb128	-4
          .byte	0x8
          .uleb128	1
          .byte	0x1B
          .byte	0xC
          .uleb128	4
          .uleb128	4
          .byte	0x88
          .uleb128	1
          .align	4
  .Leh_frame_common_end:
  
  .Lfun.eh:
          .long	.Leh_frame_end1-.Leh_frame_begin1
  .Leh_frame_begin1:
          .long	.Leh_frame_begin1-.Leh_frame_common
          .long	.Leh_func_begin1-.
          .long	.Leh_func_end1-.Leh_func_begin1
          .uleb128	0
          .byte	0xE
          .uleb128	16
          .byte	0x4
          .long	.Llabel1-.Leh_func_begin1
          .byte	0xD
          .uleb128	4
          .align	4
  .Leh_frame_end1:
  
          .text
          .globl	caml<stdin>__code_end
  caml<stdin>__code_end:
          .data
          .globl	caml<stdin>__data_end
  caml<stdin>__data_end:
          .long	0
          .globl	caml<stdin>__frametable
  caml<stdin>__frametable:
          # live roots for fun
          .long	.Llabel2
          .short	0xC
          .short	0x2
          .word	8
          .word	4
          .align	4
          .section	.note.GNU-stack,"",@progbits

So perhaps it is worth a look.

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

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Monday 11 May 2009 09:05:08 Dmitry Bely wrote:
> I think it would be the major code rewrite (if ever possible). Merging
> SSE2 from amd64 into i386 code generator took about a day of my
> efforts. How much time LLVM integration would require? If it is that
> simple can you provide a proof-of-the-concept implementation?

Well, I can provide a complete garbage collected VM. :-)

  http://hlvm.forge.ocamlcore.org/

The hard part of writing an LLVM backend for ocamlopt is probably getting LLVM 
to generate code that is compatible with OCaml's GC, particularly the stack. 
However, I believe Gordon Henriksen already did this:

  "Included in the pending LLVM garbage collection code generation  
changeset is an Ocaml frametable emitter." -
  http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-November/011527.html

Unfortunately, I will not have any spare time until my next book is out...

Did any of the OCaml+LLVM student projects get funded in the end?

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

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Andrey Riabushenko]

> Did any of the OCaml+LLVM student projects get funded in the end?

NO, Unfortunately. Not this time...

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Dmitry Bely]

On Mon, May 11, 2009 at 1:26 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> On Monday 11 May 2009 09:05:08 Dmitry Bely wrote:
>> I think it would be the major code rewrite (if ever possible). Merging
>> SSE2 from amd64 into i386 code generator took about a day of my
>> efforts. How much time LLVM integration would require? If it is that
>> simple can you provide a proof-of-the-concept implementation?
>
> Well, I can provide a complete garbage collected VM. :-)
>
>  http://hlvm.forge.ocamlcore.org/

We are talking about a new backend to Ocaml compiler, aren't we?

> The hard part of writing an LLVM backend for ocamlopt is probably getting LLVM
> to generate code that is compatible with OCaml's GC, particularly the stack.
> However, I believe Gordon Henriksen already did this:
>
>  "Included in the pending LLVM garbage collection code generation
> changeset is an Ocaml frametable emitter." -
>  http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-November/011527.html

So it's just pie in the sky. No working implementation has been
demonstrated since then. The answer to your "why not use LLVM to
replace several of the existing backends?" question is quite obvious.

- Dmitry Bely

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Dmitry Bely]

On Sun, May 10, 2009 at 7:50 AM, Jon Harrop <jon@ffconsultancy.com> wrote:
> On Sunday 10 May 2009 03:16:49 Seo Sanghyeon wrote:
>> 2009/5/10 Goswin von Brederlow <goswin-v-b@web.de>:
>> > Having ocaml require SSE2 is quite unacceptable for someone with a Via
>> > C7 cpu (they don't have SSE2, right?) Is it really that much work for
>> > ocaml to use option 3?
>>
>> Maybe not, but don't underestimate tiny inconveniences! Even if it is
>> tiny more work to support x87, it could be a difference of doing it and
>> not doing it.
>> http://lesswrong.com/lw/f1/beware_trivial_inconveniences/
>
> If you want to avoid inconvenience, why not use LLVM to replace several of the
> existing backends?

I think it would be the major code rewrite (if ever possible). Merging
SSE2 from amd64 into i386 code generator took about a day of my
efforts. How much time LLVM integration would require? If it is that
simple can you provide a proof-of-the-concept implementation?

- Dmitry Bely

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Florian Weimer]

* Goswin von Brederlow:

> Having ocaml require SSE2 is quite unacceptable for someone with a Via
> C7 cpu (they don't have SSE2, right?)

More problematic are AMD's K7 and some of their Sempron processors, I
think.  AMD introduced SSE2-less CPUs as late as 2004.

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Richard Jones]

On Sun, May 10, 2009 at 10:56:37AM +0200, CUOQ Pascal wrote:
> According to http://en.wikipedia.org/wiki/SSE2, someone using a Via C7
> should be fine.

AMD Geode then ...

$ grep -i flags /proc/cpuinfo 
flags		: fpu de pse tsc msr cx8 pge cmov mmx mmxext 3dnowext 3dnow up

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Jon Harrop]

On Sunday 10 May 2009 03:16:49 Seo Sanghyeon wrote:
> 2009/5/10 Goswin von Brederlow <goswin-v-b@web.de>:
> > Having ocaml require SSE2 is quite unacceptable for someone with a Via
> > C7 cpu (they don't have SSE2, right?) Is it really that much work for
> > ocaml to use option 3?
>
> Maybe not, but don't underestimate tiny inconveniences! Even if it is
> tiny more work to support x87, it could be a difference of doing it and
> not doing it.
> http://lesswrong.com/lw/f1/beware_trivial_inconveniences/

If you want to avoid inconvenience, why not use LLVM to replace several of the 
existing backends?

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

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Seo Sanghyeon]

2009/5/10 Goswin von Brederlow <goswin-v-b@web.de>:
> Having ocaml require SSE2 is quite unacceptable for someone with a Via
> C7 cpu (they don't have SSE2, right?) Is it really that much work for
> ocaml to use option 3?

Maybe not, but don't underestimate tiny inconveniences! Even if it is
tiny more work to support x87, it could be a difference of doing it and
not doing it.
http://lesswrong.com/lw/f1/beware_trivial_inconveniences/

-- 
Seo Sanghyeon

Re: [Caml-list] Ocamlopt x86-32 and SSE2

[Goswin von Brederlow]

"CUOQ Pascal" <Pascal.CUOQ@cea.fr> writes:

> Xavier Leroy <Xavier.Leroy@inria.fr> wrote:
>>2- Declare pre-SSE2 processors obsolete and convert the current
>>   "i386" port to always use SSE2 float arithmetic.
>>
>>3- Support both x87 and SSE2 float arithmetic within the same i386
>>   port, with a command-line option to activate SSE2, like gcc does.
>...
> In Linux distributions, is it completely forbidden to have packages
> that will not work on the bottom line?
> This is (I assume) Ocaml 3.12 that we are talking about, which
> would land sometime in 2010 and arrive in binary distributions
> that are scheduled to be released in 2011. Will Debian maintain
> its delusion of supporting the i486 by that time?
>
> Pascal

As you said (in the deleted part) there are plenty of cpus without
SSE2 around and Debian will continue to support them. That does not
really mean i486 at 25MHz will be used but it is the common bottom
line that can easily be supported.

Having ocaml require SSE2 is quite unacceptable for someone with a Via
C7 cpu (they don't have SSE2, right?) Is it really that much work for
ocaml to use option 3?

MfG
        Goswin