Native code generation and gcc

Native code generation and gcc

[Mikael Djurfeldt]

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

[I apologize beforehand for being completely out of context.]

Are there fundamental reasons for not re-using the gcc backends for native
code generation? I'm thinking of the (im?)possibility to convert the cps to
some of the intermediate languages of gcc.

If it wouldn't cause bad constraints the obvious gain is the many targets
(for free), the gcc optimizations, not having to maintain backends and free
future development.

Of course, there's the practical problem that gcc needs to be adapted for
this kind of use---but shouldn't it be adapted that way anyway? :)

Just an (old) idea...

Mikael

[-- Attachment #2: Type: text/html, Size: 896 bytes --]

Re: Native code generation and gcc

[Helmut Eller]

The following message is a courtesy copy of an article
that has been posted to gmane.lisp.guile.devel as well.

On Sat, Dec 03 2016, Mikael Djurfeldt wrote:

> Are there fundamental reasons for not re-using the gcc backends for
> native code generation? I'm thinking of the (im?)possibility to
> convert the cps to some of the intermediate languages of gcc.

Tail calls come to mind.  GCC is built around the C/C++ ABI and C
calling conventions.  Due to C's varargs, that's almost always some
variant of "caller pops arguments".  I think sibling calls can be
optimized everywhere but not general tail calls.  You could add support
for tail calls to some backends, but that's far from "for free".  The C
calling convention is also not that great for returning a (statically)
unknown number of values.

Sure, there are tricks/kludges to compile Scheme to C.  I think it would
be simpler/less risky to make a C generating backend for Guile before
going directly to GCC.  The main advantage of a direct GCC front-end
would be better control over debugging information.

Helmut

Re: Native code generation and gcc

[Greg Troxel]

Mikael Djurfeldt <mikael@djurfeldt.com> writes:

> Are there fundamental reasons for not re-using the gcc backends for native
> code generation? I'm thinking of the (im?)possibility to convert the cps to
> some of the intermediate languages of gcc.

Also there is llvm.  If there are issues, they may be different.

Re: Native code generation and gcc

[Lluís Vilanova]

Mikael Djurfeldt writes:

> [I apologize beforehand for being completely out of context.]
> Are there fundamental reasons for not re-using the gcc backends for native code generation? I'm thinking of the (im?)possibility to convert the cps to some of the intermediate languages of gcc.

> If it wouldn't cause bad constraints the obvious gain is the many targets (for free), the gcc optimizations, not having to maintain backends and free future development.

> Of course, there's the practical problem that gcc needs to be adapted for this kind of use---but shouldn't it be adapted that way anyway? :)

> Just an (old) idea...

> Mikael

Guile 2.1 has a register-base bytecode VM that makes using a code generation
library like GNU lightning [1] a convenient alternative. In fact, that's the
library used by nash [2] (an experimental Guile VM that generates native code
for hot routines). You also have the experimental GCC JIT interface [3] to
achieve similar goals (available upstream since GCC 5, I think).

IMO, if guile wants to go the tracing JIT way (like nash), it should store the
CPS representation of routines to be able to iteratively apply more heavy-weight
optimizations as the routine becomes hotter (called more frequently).

For example, you could start with the current state. If the routine is called
many times with the same argument types, you can create a version specialized
for these types, opening more unboxing possibilities (the routine entry point
would then have to be a version dispatcher). If a routine version later becomes
hotter, re-compile that version into native code.

One open question is whether the VM needs to be changed to count routine
"hotness" efficiently (as in nash), or if a simple routine prelude inserted by
guile's compiler tower could do that almost as efficiently (the bytecode ISA
might need new atomic integer operations to cope with routine tracing in a
multi-threaded app).

Also, these all are no small tasks.

[1] https://www.gnu.org/software/lightning/
[2] https://github.com/8c6794b6/guile-tjit
[3] https://gcc.gnu.org/wiki/JIT

Cheers,
  Lluis

Re: Native code generation and gcc

[Mikael Djurfeldt]

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

Many thanks for these links!

It seems like the GCC JIT interface is the kind of "adaptation" of gcc
which I asked for. :-)

Then there's the calling convention problem which Helmut brough up earlier
in this thread. But I guess there could be workarounds. In any case one
would have to look closer regarding this.

Regarding "hotness":

The original GOOPS implementation had a somewhat crazy feature that an
application of a generic function to a specific argument list first
resulted in the standard MOP procedure for finding a set of applicable
methods and, second, from this/these generated something called a "cmethod"
(compiled method) which, in turn, was stored in a cache as well as applied
to the list of arguments.

Next time this generic function was applied to an argument list with the
same type signature, the *same* cmethod as had been used the first time
could be very quickly looked up in the cache. (This lookup is described in
doc/goops.mail in the repository.)

The thought behind this was that when a cmethod is compiled, there is
knowledge about the specific types of the arguments. This means that a
compiler which compiles the applicable method into a cmethod can do some of
the type dispatch during compile time, for example that of slot access.
This is partially equivalent to unboxing, but more general, since some of
the *generic function applications* can have their type dispatch resolved
at compile time too. In the most ambitious approach one would include
return values in the cmethod type signature---something which is natural to
do when compiling to cps. (This type dispatch elimination was never
implemented in GOOPS.)

I was curious how much impact this caching scheme of things would have in
real-world programs. It turned out to work very well. I'm only aware of one
complaint on memory use. Obviously, though, if a generic function with a
longer argument list is repeatedly called with different type signatures of
the argument list, this could lead to a combinatorial explosion and fill up
memory (as well as being rather inefficient).

When Andy re-wrote GOOPS for the new compiler, the cmethod caching was
removed---a sensible thing to do in my mind. *But*, some of the downsides
of this scheme could be removed if hotness counting was added to the cache.
One could do it in various ways. One could be to initially just associate
the argument list type signature with a counter. If this counter reaches a
certain threshold, the applicable method(s) is/are compiled into a cmethod
stored in the cache. The storage of type signatures and counters still has
the combinatorial explosion problem. This could now be avoided by limiting
the size of the cache such that the counters compete for available space.
(There are further issues to consider such as adaptability through
forgetting, but I won't make this discussion even more complicated.)

Best regards,
Mikael

On Mon, Dec 5, 2016 at 5:18 PM, Lluís Vilanova <vilanova@ac.upc.edu> wrote:

> Mikael Djurfeldt writes:
>
> > [I apologize beforehand for being completely out of context.]
> > Are there fundamental reasons for not re-using the gcc backends for
> native code generation? I'm thinking of the (im?)possibility to convert the
> cps to some of the intermediate languages of gcc.
>
> > If it wouldn't cause bad constraints the obvious gain is the many
> targets (for free), the gcc optimizations, not having to maintain backends
> and free future development.
>
> > Of course, there's the practical problem that gcc needs to be adapted
> for this kind of use---but shouldn't it be adapted that way anyway? :)
>
> > Just an (old) idea...
>
> > Mikael
>
> Guile 2.1 has a register-base bytecode VM that makes using a code
> generation
> library like GNU lightning [1] a convenient alternative. In fact, that's
> the
> library used by nash [2] (an experimental Guile VM that generates native
> code
> for hot routines). You also have the experimental GCC JIT interface [3] to
> achieve similar goals (available upstream since GCC 5, I think).
>
> IMO, if guile wants to go the tracing JIT way (like nash), it should store
> the
> CPS representation of routines to be able to iteratively apply more
> heavy-weight
> optimizations as the routine becomes hotter (called more frequently).
>
> For example, you could start with the current state. If the routine is
> called
> many times with the same argument types, you can create a version
> specialized
> for these types, opening more unboxing possibilities (the routine entry
> point
> would then have to be a version dispatcher). If a routine version later
> becomes
> hotter, re-compile that version into native code.
>
> One open question is whether the VM needs to be changed to count routine
> "hotness" efficiently (as in nash), or if a simple routine prelude
> inserted by
> guile's compiler tower could do that almost as efficiently (the bytecode
> ISA
> might need new atomic integer operations to cope with routine tracing in a
> multi-threaded app).
>
> Also, these all are no small tasks.
>
> [1] https://www.gnu.org/software/lightning/
> [2] https://github.com/8c6794b6/guile-tjit
> [3] https://gcc.gnu.org/wiki/JIT
>
> Cheers,
>   Lluis
>

[-- Attachment #2: Type: text/html, Size: 6207 bytes --]

Re: Native code generation and gcc

[Stefan Monnier]

> The original GOOPS implementation had a somewhat crazy feature that an
> application of a generic function to a specific argument list first
> resulted in the standard MOP procedure for finding a set of applicable
> methods and, second, from this/these generated something called a "cmethod"
> (compiled method) which, in turn, was stored in a cache as well as applied
> to the list of arguments.

Sounds like the traditional implementation of CLOS, so I wouldn't call
that "crazy".  The reaon is/was that finding the set of applicable
methods and combining them into the resulting "cmethod" was expensive,
hence the need for a cache.


        Stefan "who does the same in Emacs's CLOS implementation"