Native Code Again

Native Code Again

[Noah Lavine]

Hello all,

Sorry for all of the discussion about native code generation. I have
another idea for how we could implement a good interface to JITed
code. I've actually been thinking it for a while and initially
dismissed it as too crazy, but now I'd like to see what you all think.

The issue this solves that there is really no portable way for C code
to do tail-calls. The ideal method of calling natively-generated code
would be for the VM to tail call the JITed code, which would then tail
call the VM when it was done. The only two ways of doing this are
asking GCC to add a tail call intrinsic (unportable) or building a
library of tail-call ASM for different platforms (more generally
useful, but also basically unportable).

However, there is a third possibility: don't have the VM be C code.
Specifically, you could construct the VM using the JITcode generator,
either on Guile startup or whenever the user decided to enable native
code generation. The benefit of this is that the VM could communicate
with native code using any method our JIT library supports, rather
than any method you can do in portable C. Also, it introduces no new
dependencies than what you need anyway for native code generation,
since you would only need to do this in cases where you would be
generating native code, and in that case you would have to have JIT
capability anyway. The downside is that it's a big new batch of code
to add to Guile.

Just so you know, I have a thought on how to implement this. I posed
here a while back about generating the VM from s-expressions, but I
now have a different idea. I think that Guile should have a C code
parser, if for no other reason than that we could parser C header
declarations and make foreign function interfaces automatically. Given
that, it wouldn't be too much more work to compile C to libjit.
Therefore, I think the path to a native-code VM is to leave the VM as
it is (except maybe reserve an opcode for native-code calls). Then I
write first a C parser for Guile and then a converter program that
would take Guile's current VM and output a JIT VM like I've described.

One downside of this is that libjit probably doesn't have as good
optimization abilities as GCC, so the VM produced might be slower.
Another issue is that this is quite a bit of complexity, but actually
most of the complexity would happen at the time we compile Guile, not
Guile runtime. By the time Guile is running, the only remaining task
should be to run libjit once and go.

So, what do you all think?

Noah

Re: Native Code Again

[Andy Wingo]

Heya Noah,

Replying out-of-order here.

On Sat 08 Jan 2011 18:27, Noah Lavine <noah.b.lavine@gmail.com> writes:

> Therefore, I think the path to a native-code VM is to leave the VM as
> it is (except maybe reserve an opcode for native-code calls). Then I
> write first a C parser for Guile and then a converter program that
> would take Guile's current VM and output a JIT VM like I've described.

Hah, it seems we concluded on the same thing after all... 

> Specifically, you could construct the VM using the JITcode generator,
> either on Guile startup or whenever the user decided to enable native
> code generation.

This is a very interesting possibility.  It scares me, in its
complexity, but it does seem to handle all of the objections that I had.

> The ideal method of calling natively-generated code would be for the
> VM to tail call the JITed code, which would then tail call the VM when
> it was done. The only two ways of doing this are asking GCC to add a
> tail call intrinsic (unportable) or building a library of tail-call
> ASM for different platforms (more generally useful, but also basically
> unportable).

I actually don't think that either of these are bad ideas.

And also... why not rely on gcc's tail-call optimization, in the case
where it works?  You can check for it at configure-time.  I just ran
some small tests for tail-calls between functions in separate
compilation units and it shows that indeed, gcc does the right thing.

I guess that given this circumstance, things are a lot easier.  The JIT
library still needs to know how to tail-call a C function, but that is
more tractable.  If you don't have tail-calls, perhaps the JIT compiler
uses trampolines as you and Ludovic proposed; and that becomes a case
that only gets exercised with -O0, and possibly not even then if we add
-foptimize-sibling-calls when available.

My apologies again for going back and forth on this issue!  It's
important, and there are a few options, so I guess more discussion is
better here.

Let us know your thoughts :)

Regards,

Andy
-- 
http://wingolog.org/

Re: Native Code Again

[Noah Lavine]

Him

>> Therefore, I think the path to a native-code VM is to leave the VM as
>> it is (except maybe reserve an opcode for native-code calls). Then I
>> write first a C parser for Guile and then a converter program that
>> would take Guile's current VM and output a JIT VM like I've described.
>
> Hah, it seems we concluded on the same thing after all...

Yeah, it seems like that's the way to go.

>> Specifically, you could construct the VM using the JITcode generator,
>> either on Guile startup or whenever the user decided to enable native
>> code generation.
>
> This is a very interesting possibility.  It scares me, in its
> complexity, but it does seem to handle all of the objections that I had.

The complexity actually scares me too. I only mentioned it because it
seemed like the cleanest way to make tail calls work. After reading
your email, though, maybe it's not worth it.

> And also... why not rely on gcc's tail-call optimization, in the case
> where it works?  You can check for it at configure-time.  I just ran
> some small tests for tail-calls between functions in separate
> compilation units and it shows that indeed, gcc does the right thing.

I don't think you want to rely on that, because then programs might
break at -O0 that would work fine at higher optimization levels.
However, if GCC added a special intrinsic function that would always
do a tail call, then that could work. And they might very well add it
if we asked them to.

> I guess that given this circumstance, things are a lot easier.  The JIT
> library still needs to know how to tail-call a C function, but that is
> more tractable.  If you don't have tail-calls, perhaps the JIT compiler
> uses trampolines as you and Ludovic proposed; and that becomes a case
> that only gets exercised with -O0, and possibly not even then if we add
> -foptimize-sibling-calls when available.

Well, the JIT library can already tail-call C code. That's the reason
I had thought of using the JIT library to generate the VM. The main
advantage of that is that tail calls would work everywhere the JIT
works, so there wouldn't be any new restrictions on what platforms
could use JIT. (Also, it frees me from having to do more work.) But
even with that advantage, it could make startup really slow, and it's
hugely complex, as you say.

I suppose ultimately the best thing would be to make C code do tail
calls. As far as I can tell, all major C compilers (gcc, icc, msvc,
llvm) support inline assembly, so it can be done. It might be easiest,
though, to do trampolines first, and then implement real tail calls
platform-by-platform. (That may have been what you were saying, too.)

Noah

Re: Native Code Again

[Andy Wingo]

Hi,

On Fri 28 Jan 2011 15:33, Noah Lavine <noah.b.lavine@gmail.com> writes:

>> And also... why not rely on gcc's tail-call optimization, in the case
>> where it works?  You can check for it at configure-time.  I just ran
>> some small tests for tail-calls between functions in separate
>> compilation units and it shows that indeed, gcc does the right thing.
>
> I don't think you want to rely on that, because then programs might
> break at -O0 that would work fine at higher optimization levels.

You can always test that the compiler supports
-foptimize-sibling-calls, and add it to CFLAGS as necessary.  In any
case you know at configure time whether it is supported or not, and can
compile accordingly.

> However, if GCC added a special intrinsic function that would always
> do a tail call, then that could work. And they might very well add it
> if we asked them to.

Even if they did, we'd have to check for it anyway.  Besides, the idiom
already exists: return foo (...);.

> Well, the JIT library can already tail-call C code.

Great.

Cool.  The plans coalesce :)

A
-- 
http://wingolog.org/

Re: Native Code Again

[Ken Raeburn]

On Jan 28, 2011, at 09:33, Noah Lavine wrote:
> 
>> And also... why not rely on gcc's tail-call optimization, in the case
>> where it works?  You can check for it at configure-time.  I just ran
>> some small tests for tail-calls between functions in separate
>> compilation units and it shows that indeed, gcc does the right thing.
> 
> I don't think you want to rely on that, because then programs might
> break at -O0 that would work fine at higher optimization levels.

It's also dependent on code-specific and machine-specific parameters that are coded into gcc; skimming some sources briefly (and keep in mind, I'm a bit rusty at this), it looks like:

 * various cases of needing different amounts of stack space for arguments
 * alpha: target must be known to use same $gp value; no indirect calls
 * arm: can't be 'long' call out of range of short branch insn; no indirect calls
 * ia64: target must be known to use same GP
 * pa: must be 32-bit mode; target must be static function in same file if not ELF; no "portable runtime"?
 * rs6000: no indirect calls; target must be static (I think?) if AIX
 * rx: no indirect calls
 * sparc: no indirect calls

There are other constraints I've ignored, for example if return registers differ (because return types are different) or some cases of PIC code generation (unless you're thinking of writing out object code to reload later?).  The requirements for no indirect calls need to be looked at platform by platform; I expect for the generated code that we would be using indirect calls, wouldn't we, with target addresses loaded from structures?

> Well, the JIT library can already tail-call C code. That's the reason
> I had thought of using the JIT library to generate the VM. The main
> advantage of that is that tail calls would work everywhere the JIT
> works, so there wouldn't be any new restrictions on what platforms
> could use JIT. (Also, it frees me from having to do more work.) But
> even with that advantage, it could make startup really slow, and it's
> hugely complex, as you say.
> 
> I suppose ultimately the best thing would be to make C code do tail
> calls. As far as I can tell, all major C compilers (gcc, icc, msvc,
> llvm) support inline assembly, so it can be done.

They probably all do, but you'd have to know how to release the stack frame, possibly restore saved registers, put the outgoing arguments into the right locations, adjust for differing numbers of arguments, etc.

> It might be easiest,
> though, to do trampolines first, and then implement real tail calls
> platform-by-platform. (That may have been what you were saying, too.)

Starting with trampolines seems like a good idea to me.

Ken