Scheme on LLVM IR

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Scheme on LLVM IR

craven
Hello!

I've been trying to implement a simple compiler from Scheme to LLVM IR,
and have run into the following problem:

In Scheme, any function can be called on any number of arguments, but it
should check at runtime for arity errors.
I haven't been able to find a way in LLVM IR to access the actual number
of parameters a function was called with.

I think the following approach might solve the problem:

- Implement a new calling convention that passes the number of arguments
  in a register, and all values in registers / the stack.
- Implement an intrinsic to get the number of arguments in LLVM IR.
- Implement an intrinsic to get at the arguments in LLVM IR.

Are there any better ways to solve this? Does any of the existing
calling conventions support this?

Incidentially, the same handling is necessary for return values (any
function can return any number of values, and the caller must check for
correct return value arity).

Varargs seem a bad match, as everything is passed on the stack, not in
registers, and no count is kept of the actual number of arguments.

Am I correct that in order to implement this, I'd need to add the new
calling convention and intrinsics for each Target separately?

Thanks for any help or suggestions!

Peter
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Scheme on LLVM IR

Tim Northover-2
Hi Peter,

> Are there any better ways to solve this? Does any of the existing
> calling conventions support this?

Can't you handle this entirely in the front-end? Just decide by fiat
that all of your scheme functions will take an extra (hidden to the
Scheme users) parameter saying how many args they were given. That's
how C++ deals with the implicit "this" parameter for class methods.

Then you could either use varargs or bitcast your functions to a
reasonable type when used.

> Incidentially, the same handling is necessary for return values (any
> function can return any number of values, and the caller must check for
> correct return value arity).

A similar approach could work there, though targets aren't used to
dealing with lots of return values so you may encounter more problems
(i.e. LLVM bugs).

> Varargs seem a bad match, as everything is passed on the stack, not in
> registers, and no count is kept of the actual number of arguments.

Is that on x86-32 Windows? In almost all other cases varargs are
passed in a manner compatible with non-variadic functions -- there's
just too much bad software out there that relies on this (it was
allowed in the bad old K&R C days) so ABIs are designed with that in
mind.

But you're right about them not usually keeping count.

Cheers.

Tim.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Scheme on LLVM IR

craven
> Can't you handle this entirely in the front-end? Just decide by fiat
> that all of your scheme functions will take an extra (hidden to the
> Scheme users) parameter saying how many args they were given. That's
> how C++ deals with the implicit "this" parameter for class methods.

> Then you could either use varargs or bitcast your functions to a
> reasonable type when used.

Thanks for pointing out the obvious! This never crossed my mind, but it
should work well! I'll try to implement this, and see where it leads me
:)

One especially problematic function seems to be APPLY. It takes a
function and a list of values as parameters, and applies the function to
the values [as in (apply + '(1 2 3)) -> (+ 1 2 3)]. So if varargs adhere
to the standard ABI, I could just cast the function to varargs
parameters, then call it, and (with the arity checking you described
above), things should work correctly?

>> Varargs seem a bad match, as everything is passed on the stack, not in
>> registers, and no count is kept of the actual number of arguments.
>
> Is that on x86-32 Windows? In almost all other cases varargs are
> passed in a manner compatible with non-variadic functions -- there's
> just too much bad software out there that relies on this (it was
> allowed in the bad old K&R C days) so ABIs are designed with that in
> mind.

That's what I tested, I'll try other targets too, to see what code they
generate.

Thanks for the swift help!

Peter
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Scheme on LLVM IR

Tim Northover-2
> One especially problematic function seems to be APPLY. It takes a
> function and a list of values as parameters, and applies the function to
> the values [as in (apply + '(1 2 3)) -> (+ 1 2 3)]. So if varargs adhere
> to the standard ABI, I could just cast the function to varargs
> parameters, then call it, and (with the arity checking you described
> above), things should work correctly?

Probably not, unfortunately. The problem is that there's no LLVM
CallInst with a variable number of arguments at runtime. A couple of
ugly solutions spring to mind, but nothing very elegant.

You could have a maximum number of arguments and implement @apply
something like:

define %whatever @apply(i32 %numArgs, %valType %func, %valType %argList) {
  Check %numArgs = 2
  if (length %argList) = 0
    %callee = bitcast %valType %func to %whatever(i32)*
    call %whatever(i32)* %callee(i32 0)
  else if (length %argList) = 1
    %callee = bitcast %valType %func to %whatever(i32, %valType)*
    %arg1 = (extract from %argList)
    call %whatever(i32, %valType)* %callee(i32 1, %valType %arg1)
  ...
}

Another possibility would be to implement apply in assembly (that has
the advantage that you could put a loop in once you reach stack
arguments to support as many as are needed).

The only neat LLVM solution I can think of would be to use a less
efficient calling convention where arguments are really pointers off
somewhere else and every function has the prototype %whatever(i32
%numArgs, valType* %args).

But I've not actually implemented a dynamic language like Scheme.
Others around here have, and they may have better ideas. Fingers
crossed they'll pipe up.

Tim.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev